LintCode 511: Swap Two Nodes in Linked List (链表好题)

511 · Swap Two Nodes in Linked List
Algorithms
Medium

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

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

Example
Example 1:

Input: 1->2->3->4->null, v1 = 2, v2 = 4
Output: 1->4->3->2->null
Example 2:

Input: 1->null, v1 = 2, v2 = 1
Output: 1->null
Tags
Related Problems

451
Swap Nodes in Pairs
Easy

解法1：加个dummyHead，然后分两种情况处理：

1. v1和v2不相连
2. v1和v2相连 //这个情况一定要单独处理，不然pre1可能就是v2，或者pre2可能就是v1，会陷入endless loop。

/**
 * 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
     * @param v1: An integer
     * @param v2: An integer
     * @return: a new head of singly-linked list
     */
    ListNode* swapNodes(ListNode *head, int v1, int v2) {
        if (head == nullptr) return nullptr;
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *node = dummyHead;
        ListNode *pre1 = nullptr, *node1 = nullptr, *pre2 = nullptr, *node2 = nullptr;
        while (node->next) {
            if (node->next->val == v1) {
                pre1 = node;
                node1 = node->next;
            } else if (node->next->val == v2) {
                pre2 = node;
                node2 = node->next;
            }
            if (node1 && node2) break;
            node = node->next;
        }
        if (!node1 || !node2) return head;
        if (node1->next != node2 && node2->next != node1) {
            ListNode *saveNode2Next = node2->next;
            pre1->next = node2;
            node2->next = node1->next;
            pre2->next = node1;
            node1->next = saveNode2Next;
        } else { //node1 and node2 are in sequential
            if (node1->next == node2) {
                pre1->next = node2;
                node1->next = node2->next;
                node2->next = node1;
            } else {
                pre2->next = node1;
                node2->next = node1->next;
                node1->next = node2;
            }
        }
        return dummyHead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59