24. 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.

Difficulty: Medium

解法1

迭代.建立dummy结点(注意之后释放该结点),拿1,2,3,4举例,第一次循环pre=dummy,将1指向3,将2指向1,再将pre设为1

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode(-1),*pre = dummy;
        dummy->next = head;
        while (pre->next && pre->next->next)
        {
            // t=2
            ListNode* t = pre->next->next;
            // 1 ->(指向next) 3
            pre->next->next = t->next;
            // 2 -> 1
            t->next = pre->next;
            // pre(dummy) -> t
            pre->next = t;
            // pre = 1
            pre = t->next;
            
            //所以第一次while循环后的结果为
            //dummy-> t(2) -> 1 -> 3
            //pre = 1 然后到下一次循环
        }
        ListNode* res = dummy->next;
        delete dummy;
        dummy = NULL;
        return res;
    }
};

解法2

递归,先递归到最后两个进行交换,再依次向前迭代.

ListNode* swapPairs(ListNode* head)
{
    if (!head || !head->next) return head;
    ListNode *t = head->next;
    head->next = swapPairs(head->next->next);
    t->next = head;
    return t;
}
 
comments powered by Disqus