Given a linked list, swap every two adjacent nodes and return its head.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
两两反转链表节点
这题思路是 两两反转。、所以每次处理 2个节点
while cur and cur.next:
a,b,c = cur,cur.next,cur.next.next
b-->a
a->c
cur = c
这时我们就完成了 两两(cur <=> cur.next)反转,并成功迭代到下一个pairs .
但我们发现,cur.next 也就是上面的b, 做为新的head 与之前的链表断开了。
比如 例子中 2->1->3->4 , 当cur =3 是, while 会完成 4->3->null,前面的 2->1 就和4->3 断开了。
所以 我们需要一个指针last 来表示更新之前反转完毕链表的尾巴( 也就是例子中上一次迭代中“2->1” 的“1”), 并将last ->b,这样就接上了, 所以 我们每次迭代就更新 last 等于上述的a 。 这边有个特殊的情况, 头一对pair 不存在前面的链表尾巴, 所以直接 将头 赋值给 head 就OK了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next){
return head;
}
ListNode* cur = head;
ListNode* last = head;
while(cur && cur->next){
ListNode* newHead =cur->next;
ListNode* next = newHead->next;
newHead->next = cur;
cur->next = next;
if (last !=cur ){
last->next = newHead;
}else{
head = newHead;
}
last = newHead->next;
cur = next;
}
return head;
}
};
image.png
网友评论