LeetCode - 1721 - 交换链表中的节点 - Java - 两种解法

• 题目
• 题目解析
• 解题思维一 （交换两个节点val值）
• • 第一步： 新建一个傀儡头节点，使其 next 存储 head 的地址
  • 重点：寻找逆序 第 k 个节点：利用快慢指针。
  • 代码如下
• 解题思维二（交换两个节点的位置）
• • 代码如下：

题目的意思很明确，就是将 两个节点 进行交换。
既然是交换，我们就是可以有两个思维：1.交换器两个节点的值，已达到想要的结果。2.按照传统模式，交换两个节点的位置，来达到效果。

难点：寻找 正序第k 个 节点 和 逆序第 k 个节点

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode newHead = new ListNode(0,head);
        ListNode fast = newHead;
        ListNode slow = newHead;
        for(int i = 0;i < k;i++){
            fast = fast.next;
            if(fast == null){
                return newHead.next;
            }
        }
        ListNode fastCur = fast;
        while(fastCur!=null){
            fastCur =fastCur.next;
            slow = slow.next;
        }
        int tmp = fast.val;
        fast.val = slow.val;
        slow.val = tmp;
        return newHead.next;
    }
}

第二种解法是建立在 第一种解法的基础上。
多了 两个个前驱节点， fastPrev 和 slowPrev。
因为，我们都知道交换链表中两个节点的位置，需要借助前驱节点 ，才能完成。（实际是借助了三个节点的地址，fast 和 slow 指向的节点还有一个next存储着下一个节点的地址）

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode newHead = new ListNode(0,head);
        ListNode fast = newHead;
        ListNode slow = newHead;
        ListNode fastPrev = null;
        ListNode slowPrev = null;
        for(int i = 0;i < k;i++){
            fastPrev = fast;
            fast = fast.next;
            if(fast == null){
                return newHead.next;
            }
        }
        ListNode fastCur = fast;
        while(fastCur!=null){
            fastCur =fastCur.next;
            slowPrev = slow;
            slow = slow.next;
        }
        ListNode fastNext = fast.next;
        ListNode slowNext = slow.next;
        if(fastNext == slow){
            fast.next = slowNext;
            slow.next = fast;
            fastPrev.next = slow;
        }else if(slowNext == fast){
            slow.next =fastNext;
            fast.next = slow;
            slowPrev.next =fast;
        }else{
            slow.next = fastNext;
            fastPrev.next = slow;

            fast.next = slowNext;
            slowPrev.next = fast;
        }
        return newHead.next;
    }
}