嗨客网搜索
反转链表

题目

力扣第 206 题,反转链表,示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路

链表反转的效果如下:

01_链表反转.png

要实现这样的功能,我们的思路是我们使用两个指针,分别为 pre 指向要当前要反转的前一个结点,cur 指向当前要反转的指针,初始化时,我们需要反转第一个结点和第二个结点,因此,此时 pre 指针指向 NULL,cur 指针指向结点 1,那么指针位置如下:

02_链表反转.png

同时,我们在反转时,防止反转结点的丢失,我们需要使用一个辅助指针 temp 保存当前结点的下一个结点,那么,指针的位置如下图所示:

03_链表反转.png

现在,我们只需要将 cur 的 next 指针指向 pre 即可,如下图所示:

04_链表反转.png

接着,我们将 pre 指针指向 cur,如下图所示:

05_链表反转.png

最后,我们把 cur 再次指向 temp,如下图所示:

06_链表反转.png

此时,就完成了第一个结点的反转,现在我们进入第二个结点循环时,直接将 temp 结点后移一位即可,此时,链表结构如下:

07_链表反转.png

此时,我们再次将 cur 的 next 指针指向 pre,如下图所示:

08_链表反转.png

接着,再次将 pre 指向 cur,如下图所示:

09_链表反转.png

最后,我们把 cur 再次指向 temp,如下图所示:

10_链表反转.png

我们看到,第二次循环之后,我们已经完成了两个结点的反转,一直循环到最后一个结点即可。

代码具体实现

C语言版本

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head){ //初始化时,pre指针为空 struct ListNode* pre = NULL; //cur指针指向head struct ListNode* cur = head; //如果 cur 指针不为空,则一直循环 while(cur != NULL){ //首先,使用 temp 指针保存 cur 结点的下一个结点 struct ListNode* temp = cur->next; //cur的 next 指针指向 pre,也就是反转 cur->next = pre; //pre 指向 cur,也就是实现了将 pre 指针后移一位 pre = cur; // cur 指向 temp,同样,也是实现了 cur 指针的后移 cur = temp; } //最后循环结束了,此时 cur 为空了,因此,我们应该返回 pre 结点 return pre; }

Java版本

遍历

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null){ return head; } //定义一个当前要被替换的节点,从第二个节点开始 ListNode currentNode = head.next; //被替换的节点的前一个节点 ListNode preNode = head; preNode.next = null; while (true) { //获取当前节点的下一个节点 ListNode nextNode = currentNode.next; //将前一个节点追加到当前节点后面 currentNode.next = preNode; //遍历循环到最后一个节点 if (nextNode == null) { return currentNode; } //将当前要操作的节点和前一个节点重新设置,往后挪动指针 preNode = currentNode; currentNode = nextNode; } } }

递归

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } * 在整理思绪的时候,我们会发现前一个节点和后一个节点在进行节点交换的时候,做的事情是一样的将当前节点和后面一个节点交换,然后将当前节点的后指针指向剩下的节点。 */ class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null){ return head; } ListNode node1 = head; ListNode node2 = head.next; node1.next = null; ListNode retNode = revertNode(node1, node2); return retNode; } private ListNode revertNode(ListNode node1,ListNode node2){ ListNode retNode = null; //获取剩下的节点,剩下的节点将要和当前节点执行重复操作 ListNode node3 = node2.next; if (node3 != null) { //重置当前节点的后一个节点 node2.next = node1; //将当前节点和剩下的节点调换位置 retNode = revertNode(node2, node3); } else { node2.next = node1; retNode = node2; } return retNode; } }

Go语言版本

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseList(head *ListNode) *ListNode { //初始化时,pre指针为空 var pre *ListNode //cur指针指向head cur := head //如果 cur 指针不为空,则一直循环 for(cur != nil){ //首先,使用 temp 指针保存 cur 结点的下一个结点 temp := cur.Next //cur的 next 指针指向 pre,也就是反转 cur.Next = pre //pre 指向 cur,也就是实现了将 pre 指针后移一位 pre = cur // cur 指向 temp,同样,也是实现了 cur 指针的后移 cur = temp } //最后循环结束了,此时 cur 为空了,因此,我们应该返回 pre 结点 return pre; }

赞助商链接:


嗨客网顶部