美文网首页
[leetcode] 24 swap nodes in pair

[leetcode] 24 swap nodes in pair

作者: Kevifunau | 来源:发表于2018-10-08 23:12 被阅读0次

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

相关文章

网友评论

      本文标题:[leetcode] 24 swap nodes in pair

      本文链接:https://www.haomeiwen.com/subject/bhssaftx.html