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，然后分两种情况处理：
class Solution {
public:
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 {
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;
}
};
Original: https://blog.csdn.net/roufoo/article/details/127808721
Author: 纸上得来终觉浅 绝知此事要躬行
Title: LintCode 511: Swap Two Nodes in Linked List (链表好题)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/657844/
转载文章受原作者版权保护。转载请注明原作者出处！