leetcode: Swapping Nodes in a Linked List

1. 题目描述

You are given the head of a linked list, and an integer k.Return the head of the linked list after swapping the values of the kth node 
from the beginning and the kth node from the end (the list is 1-indexed).

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

Constraints:

The number of nodes in the list is n.
1 <= k <= n <= 105
0 <= Node.val <= 100

2. 题目解答

class Solution {
public:ListNode* swapNodes(ListNode* head, int k) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* A_ = findNodeA_(dummy, k);cout<<A_->val<<endl;ListNode* A  = A_->next;ListNode* B_ = findNodeB_(dummy, k);ListNode* B  = B_->next;cout<<A_->val<<" "<<A->val<<" "<<B_->val<<" "<<B->val<<endl;if(B->next == A){ListNode* temp = A->next;B_->next = A;A->next = B;B->next = temp;}else if(A->next == B){ListNode* temp = B->next;A_->next = B;B->next = A;A->next = temp;}else{ListNode* temp = B->next;A_->next = B;B->next = A->next;B_->next = A;A->next = temp;}return dummy->next;}
private:ListNode* findNodeA_(ListNode* dummy, int k){ListNode* temp = dummy;while(k-- > 1){temp = temp->next;}return temp;}ListNode* findNodeB_(ListNode* dummy, int k){ListNode* temp_pre = dummy;ListNode* temp_after = dummy;while(k-- > 0){temp_pre = temp_pre->next;}while(temp_pre->next != nullptr){temp_pre = temp_pre->next;temp_after = temp_after->next;}return temp_after;}
};

3. 总结

  第一步：如果在已经做了leetcode: Remove Nth Node From End of List这道题目，或者在已经知道dummy节点trick的基础上，应该会有一个大概的思路，可以写出findNodeA_和findNodeB_。其中A_表示k-1th元素，A表示kth元素；B_表示倒数k+1th元素，B表示倒数kth元素。
  第二步：通过举一个特例，可以写出交换两个节点的代码：

A_->next = B;
B->next = A->next;
B_->next = A;
A->next = temp;

  在写第二步代码的时候

原始代码	不成环的条件	推论
A_->next = B	A_ != B	B->next != A
B->next = A->next	B != A->next	A->next != B
B_->next = A	B_ != A	A->next != B

  这也就是第三步写出如下代码的来源：

        if(B->next == A){ListNode* temp = A->next;B_->next = A;A->next = B;B->next = temp;}else if(A->next == B){ListNode* temp = B->next;A_->next = B;B->next = A;A->next = temp;}