• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

206. 反转链表

开发技术 开发技术 4小时前 2次浏览
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *cur = head;
    struct ListNode *tail = NULL;
    struct ListNode *temp = NULL;

    while(cur != NULL){
        temp = cur->next;//保存下一个结点
        cur->next = tail;//确定当前结点的next结点,也就是确定新链表的尾结点
        tail = cur;//确定新链表的头结点
        cur = temp;//确定下一个需要处理的结点
    }

    return tail;
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode tail=null;
        ListNode temp=null;
        while (cur != null) {
            temp = cur.next;
            cur.next = tail;
            tail = cur;
            cur = temp;
        }
        return tail;

    }
}

这一题属于逻辑题。要弄清楚先后顺序。

肯定是要遍历链表的。
那么就看怎么处理这些结点的关系了。主要看如何处理当前结点和下一个结点的关系了。
那我们来看该怎么处理。

一般来说,题目给出的链表头结点,我们不要去动它。然后我们就有两种策略了:

  • 第一种,使用一个变量指向head
  • 第二种,new一个新的结点,使其next指向head。

两种策略要根据需要自行选择。
本题,我们使用第一种。

因为我们需要直接遍历这个链表,所以直接使用cur这个变量直接指向head。我们接下来操作这个cur变量就可以了。(cur是current的缩写,表示当前的意思)

对于本题,反转,意味着使前后结点的关系发生改变。
那么肯定需要同时持有两个结点。
所以,我们在处理cur之前,肯定要持有cur后面的一个结点。
那么我们就需要一个temp变量来持有cur.next:

temp=cur.next;

好了。现在我们持有了cur指向了head,temp指向了head.next。
接下来:
我们需要让第一个结点(也就是当前结点的next指向null,因为是第一个结点,所以反转后,第一个结点肯定就变成最后一个结点了,新链表的最后一个结点的next肯定是null)

此外,我们还需要注意一点,遍历链表的过程中,需要把temp(cur)的结点next应该要指向新链表的头结点。

那么我们需要怎么来表示这个新链表的头结点呢??

目前的cur还是在链表的左侧,temp在链表的右侧。现在cur的next还是temp

这里我们需要引入一个新的变量,使其作为新链表的头结点。使用pre表示。pre=null;
pre一开始是新链表的头结点(此时它只是一个指针,无实际内存),这个pre就是cur的next,这个时候cur.next就是pre了(cur.next=pre),这样,cur就变成新链表的第一个结点了。
然后使pre替换cur,pre=cur;

这个时候注意,已经存在两个链表了,即pre(cur)的新链表,和temp打头的旧链表。目前两个链表没有任何关系了。

重要的一步来了,我们让cur指向temp的结点上。

null<-[pre] [cur]->[]->[]

上面就是两个链表的表示形式。

现在我们继续循环处理cur就可以了
null<-[]<-[pre] [cur]->[]

主要的难点是设置一个pre作为新链表的头。
初始化的时候pre是指向null的,而不是new出来的一个新结点。


程序员灯塔
转载请注明原文链接:206. 反转链表
喜欢 (0)