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.

经典解法:设一个哨兵然后前两个互换之后到后两个。

public ListNode SwapPairs(ListNode head) {
         if (head == null) return head;
            var sentinel = new ListNode(-1);
            sentinel.next = head;
            var dummy = sentinel;
            while (head != null && head.next != null)
            {
                dummy.next = head.next;
                head.next = head.next.next;
                dummy.next.next = head;
                dummy = head;
                head = head.next;
            }
  
            return sentinel.next;
        /*ListNode sentiential = new ListNode(0);
        sentiential.next = head;
        ListNode p = head;
        ListNode d = sentiential;
        while (p != null && p.next != null) {
        d.next = p.next;
        d = p;
        p = p.next.next;
        d.next.next = d;
    }
    d.next = p;
    return sentiential.next;*/
    }

这个地方我一开始犯了一个错误是,即把注释掉的那行放在了下面.

public ListNode SwapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        var sentinel = new ListNode(-1);
        sentinel.next = head;
        var dummy = sentinel;
        while(head != null && head.next != null) 
        {
            sentinel.next =  head.next;
            //head.next = head.next.next;
            sentinel.next.next = head;
            sentinel = head;
            head.next = head.next.next;
            head = head.next;
            
        }
        return dummy.next;
    }

这个会使出现问题，head 为1。

sentinel.next = head.next;

=> sentinel.next 为2

sentinel.next.next = head;

=> 2.next = head = 1;
此时1.next依然为2. 则1.next 为2，2.next 为1，deadlock.需要先将head.next 重新赋值.

或者将list 间隔split成两个list，然后再逐个拼起来。

public ListNode SwapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        var sec = head.next;
        var sentinel = new ListNode(-1);
        var dummy = sentinel;
        var headSentinel = head;
        ListNode nextNode = null;
        ListNode nextSNode =null;
        while(head != null && head.next != null)
        {
            sentinel.next = head.next;
            head.next = head.next.next;
            sentinel =  sentinel.next;
            head = head.next;
        }
        var front  = dummy.next;
        var second = headSentinel;
        while(front != null)
        {
            nextNode = front.next;
            nextSNode = second.next;
            front.next = second;
            second.next = nextNode;
            front = nextNode;
            second = nextSNode;
        }
       
        return dummy.next;
    }

24. Swap Nodes in Pairs

相关推荐