Leetcode 链表反转套路
我们先从该套路的一个最简单的情况说起,也就是206.Reverse Linked List。它是该套路的一个最简单的的情况,怎么个简单法呢?只需要一个循环即可解决问题。
那具体是怎么解决的呢?
假设虚拟头结点对应的值为-1,我们要反转的链表为1->2->3->4。连接起来即就是-1->1->2->3->4。
假设prev->-1, cur -> 1, nex->2,第一次循环结果为-1->2->1->3->4
prev->-1, cur ->1, nex -> 3,第二次循环结果为-1->3->2->1->4
prev->-1, cur ->1, nex-> 4,第三次循环结果为-1->4->3->2->1
是什么样的效果呢?就是让nex变为head, 并且让nex和cur不断的向前走。
cur->next = nex->next; //这一步是为了让nex不断前进做准备 nex->next = prev->next; //是确保nex作为头结点后面元素的顺序,即让之前最前面的头结点位置变为第二个结点 prev->next = nex; //nex作为头结点 nex = cur->next; //nex不断前进
其中第1步和第4步有关系,也就是说第一步是为了第4步做准备(使得nex前移)
第二步是形成链表中的第二个连接。
第三步是形成链表中的第一个连接。
并且保持prev不变。
有个小小的规律就是每一步的右边步骤成了下一步的左边步骤。
第一次循环:
step2:-1 2->1>-3->4
step3:-1->2->1->3->4
prev->-1, cur -> 1, nex->2,第一次循环结果为-1->2->1->3->4
第二次循环:
step2:-1 3->2>-1->4
step3:-1->3->2->1->4
prev->-1, cur ->1, nex -> 3,第二次循环结果为-1->3->2->1->4
第三次循环:
step2:-1 4->3>-2->1
step3:-1->4->3->2->1
prev->-1, cur ->1, nex-> 4,第三次循环结果为-1->4->3->2->1
完整的代码如下所示:
class Solution { public: ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* prev = dummyHead; ListNode* cur = prev->next; ListNode* nex = cur->next; while(nex) { cur->next = nex->next; nex->next = prev->next; prev->next = nex; nex = cur->next; } ListNode* retHead = dummyHead->next; delete dummyHead; return retHead; } };
有关交换的思考:
交换a和b元素的内容:
int a, b, t; t = a; a = b; b = t;
cur->next = nex->next; nex->next = prev->next; prev->next = nex; nex = cur->next;
是否和上述内容有点类似之处呢?具体内容可以思考思考。
优质内容筛选与推荐>>