Problem

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

Given1->2->3->4->nulland v1 =2, v2 =4.

Return1->4->3->2->null.

思路

• 由于头节点有可能被调换, 所以需要dummy node
• 分别找到这两个节点的上一个节点
• 先调换两个prev节点的next节点, 再调换target节点的next节点, 不然会出现死循环

    public ListNode swapNodes(ListNode head, int v1, int v2) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;
        ListNode preV1 = null;
        ListNode preV2 = null;

        while (node != null && node.next != null) {
            if (node.next.val == v1) {
                preV1 = node;
            }
            if (node.next.val == v2) {
                preV2 = node;
            }
            node = node.next;
        }
        if (preV1 != null && preV2 != null) {
            ListNode node1 = preV1.next;
            ListNode node2 = preV2.next;
            preV1.next = node2;
            preV2.next = node1;
            ListNode temp = node1.next;
            node1.next = node2.next;
            node2.next = temp;
        }
        return dummy.next;
    }

错误版本

    public ListNode swapNodes(ListNode head, int v1, int v2) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;
        ListNode preV1 = null;
        ListNode preV2 = null;

        while (node != null && node.next != null) {
            if (node.next.val == v1) {
                preV1 = node;
            }
            if (node.next.val == v2) {
                preV2 = node;
            }
            node = node.next;
        }
        if (preV1 != null && preV2 != null) {
            ListNode node1 = preV1.next;
            ListNode node2 = preV2.next;
            ListNode temp = node1.next;
            node1.next = node2.next;
            node2.next = temp;
            preV1.next = node2;
            preV2.next = node1;
        }
        return dummy.next;
    }