451. Swap Nodes in Pairs

Code(Language:C++)

Description

中文English




Given a linked list, swap every two adjacent nodes and return its head.





Have you met this question in a real interview?  






Example




Example 1:
Input: 1->2->3->4->null
Output: 2->1->4->3->null



/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: a ListNode
     * @return: a ListNode
     */
    ListNode * swapPairs(ListNode * head) {
        // write your code here
        // 1, divided into two list nodes
        // 2, merge 
        if(head == NULL || head->next == NULL){
            return head; 
        }
        ListNode *head1 = head; 
        ListNode *head2 = head->next;
        ListNode *head1Copy = head1; 
        ListNode *head2Copy = head2; 
        while(head1 != NULL && head1->next != NULL && head2 != NULL && head2->next != NULL){
            head1->next = head1->next->next; 
            head1 = head1->next; 
            
            head2->next = head1->next; 
            head2 = head2->next; 
        }
        if(head1 != NULL && head1->next != NULL){
            head1->next = NULL; 
        }
        return merge(head2Copy, head1Copy); 
        
    }
    ListNode *merge(ListNode *l1, ListNode *l2){
        ListNode *dummy = new ListNode(0); 
        ListNode *copy = dummy; 
        while(l1 != NULL && l2 != NULL){
            dummy->next = l1;
            ListNode *temp = l1->next;
            //l1->next = l2; //用这种形式，不要用下面的。这种形式很清楚的能看出// 链条的样式，有助于先把现场保存             ListNode *temp = l1->next;
//下面的方式不利于保存现场
            dummy->next->next = l2; 
            dummy = l2; 
            l1 = temp; 
            l2 = l2->next; 
        }
        if(l1 != NULL){
            dummy->next = l1; 
        }
        if(l2 != NULL){
            dummy->next = l2; 
        }
        return copy->next; 
    }
};
二刷 2019年03月28日22:24:50 痛苦。之前做出来的，反而做不出来   ListNode * swapPairs(ListNode * head) {
        // write your code here
        //要用dummy, 要打断三个link，也就重建三个link。dummy->1->2->3,变成dummy -> 2->1->3 
        if(head == NULL || head->next == NULL){
            return head; 
        }
        ListNode *dummy = new ListNode(0);
        dummy->next = head; 
        ListNode *pre = dummy;
        while(head != NULL && head->next != NULL){
            ListNode *temp = head->next->next; 
            head->next->next = head; //重建第一个link
            pre->next = head->next; //重建第二个link
            head->next = temp; //重建第三个link
            
            pre = head;//更新，准备下一次的重建
            head = temp; 
        }
        return dummy->next; 
    }