Swap Two Nodes in Linked List 511

Question

Given a linked list and two values v1 and v2. Swap the two nodes in the linked list with values v1 and v2. It's guaranteed there is no duplicate values in the linked list. If v1 or v2 does not exist in the given linked list, do nothing.

Notice

You should swap the two nodes with values v1 and v2. Do not directly swap the values of the two nodes.

Example

Given 1->2->3->4->null and v1 = 2, v2 = 4.

Return 1->4->3->2->null.

Solution

先找第一个node和它parent，再找第二个node和它parent，再进行交换。用一个dummy node记录head，在寻找过程中一旦发现无法找到其中一个node，就返回head。最后在交换时，需要判断第一个node的下一个节点是不是第二个node。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @oaram v1 an integer
     * @param v2 an integer
     * @return a new head of singly-linked list
     */
    public ListNode swapNodes(ListNode head, int v1, int v2) {
        // Write your code here
        if(head == null){
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        //先找第一个
        while(head.next != null && head.next.val != v1 && head.next.val != v2){
            head = head.next;
        }

        if(head.next == null){
            return dummy.next;
        }

        ListNode firstParent = head;
        ListNode first = head.next;
        //再找第二个
        if(head.next.val == v1){
            while(head.next != null && head.next.val != v2){
                head = head.next;
            }
        }else{
            while(head.next != null && head.next.val != v1){
                head = head.next;
            }
        }

        if(head.next == null){
            return dummy.next;
        }

        ListNode secondParent = head;
        ListNode second = head.next;
        ListNode secondNext = second.next;

        //判断first和second是不是相连
        if(first.next == second){
            firstParent.next = second;
            second.next = first;
            first.next = secondNext;
        }else{
            firstParent.next = second;
            secondParent.next = first;
            second.next = first.next;
            first.next = secondNext;
        }

        return dummy.next;
    }
}