题目
解析
这个题目有如下的几个问题需要解决：
- 如何在遍历链表时找到两个需要被交换的节点位置
从头开始的第k个节点很好找，从结尾开始的第k个节点比较难找。比较笨的办法是先遍历一边列表，拿到长度，根据长度确定后面那个的位置。比较聪明的办法在下面解法会讲到 - 找到后如何交换
交换的话就会需要定位到两个节点分别的前后节点，实际上只需要两个节点的前面节点，后面可以通过next得到 - 如何处理特殊情况
有三种特殊情况需要处理
解法1：交换值
首先这边讲下比较聪明的定位从结尾开始的第k个节点。第一种方法：先便利找到顺向的第k个节点，从这个结点开始，向后走到结尾的步数（len-k）正好能让头节点走到逆向的第k节点。第二种方法·：记录走的步数cnt，如果步数小于k，移动头节点直到找到顺向第k个节点；如果步数大于k，移动头节点直到找到逆向第k个节点（刚好会是len-k步）；两种方法本质还是一样的
然后暴力的直接交换两个节点的位置。当然这是一种接近作弊的解法，不能体现这道题目的精髓
class Solution {
public:ListNode* swapNodes(ListNode* head, int k) {
if(!head || !head->next){
return head;}ListNode* left = head;ListNode* right = head;// find the kth node from beginningfor(int i=1;i<k;i++){
left = left->next;}// find the kth node from the endListNode* curr = left;while(curr->next){
curr = curr->next;right = right->next;}/* // alternative way of finding two nodesint cnt = 1;ListNode* curr = head;while(curr){if(cnt < k){left = left->next;}if(cnt > k){right = right->next;}curr = curr->next;cnt++;}*/int tmp_val = left->val;left->val = right->val;right->val = tmp_val;return head;}
};
解法2：实际交换节点
通过keep track of两个节点的前面节点来做到交换
难点在于需要处理三种特殊情况，在下面代码中都有详细注释。主要是两个节点相邻的特殊情况以及k超过一半的链表长度的特殊情况
class Solution {
public:ListNode* swapNodes(ListNode* head, int k) {
if(!head || !head->next){
return head;}// define dummy node for return the resultListNode* dummy = new ListNode(-1);dummy->next = head;// define the target left node to be swapped and the node beforeListNode* preLeft = dummy;ListNode* left = head;// define the target right node to be swapped and the node beforeListNode* preRight = dummy;ListNode* right = head;// find the the kth node from the beginningfor(int i=1;i<k;i++){
preLeft = preLeft->next;left = left->next;}// find the kth node from the end// trick here is that if the right start from the head of the list, when the left node reaches the end node, the right reaches the kth last nodeListNode* curr = left;while(curr->next){
curr = curr->next;preRight = preRight->next;right = right->next;}if(right == preLeft){
// note the the 1 <= k <= n, so that the right node can be on the left of left node// ...preRight->right->left...right->next = left->next;preRight->next = left;left->next = right;}else if(left == preRight){
// ...preLeft->left->right...left->next = right->next;preLeft->next = right;right->next = left;}else{
// normal case:...preLeft->left->...->preRight->right... or ...preRight->right->...->preLeft->left...ListNode* tmp = left->next;left->next = right->next;preRight->next = left;preLeft->next = right;right->next = tmp;}return dummy->next;}
};