Thursday, November 20, 2014

[LeetCode] Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

思路:

和reverse linked list很像,只不过每次reverse两个节点。同样要考虑奇偶数长度的情况。并且由于头节点会变动,dummy节点又能派上用场了。

奇数:
1->2->3
2->1->3

偶数
1->2->3->4
2->1->4->3

要constant space所以不能用递归。那就用一个指针p边扫描边reverse。用一个子函数来完成reverse pair并接回原链表的操作,返回值为pair的尾部,也就是p下一个移动位置。

D->1->2->3->4
 |
p          

D->2->1->3->4
             |
             r = swapNodes(p->next)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        while(head) head = swapNodes(head->next);
        head = dummy->next;
        delete dummy;
        return head;
    }
    
    ListNode *swapNodes(ListNode *&head) {
        if(!head || !head->next) return NULL;
        ListNode *tail = head;
        ListNode *nextHead = head->next->next;
        head = head->next;
        head->next = tail;
        tail->next = nextHead;
        return tail;
    }
};


不用子程序也可以用三指针扫描来完成:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *prev = dummy, *cur = head;
        
        while(cur && cur->next) {
            prev->next = cur->next;
            cur->next = cur->next->next;
            prev->next->next = cur;
            prev = cur;
            cur = cur->next;
        }
        
        return dummy->next;
    }
};

No comments:

Post a Comment