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

文章目录

题目

题目解析

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

解题思维一 （交换两个节点val值）

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

第一步： 新建一个傀儡头节点，使其 next 存储 head 的地址

重点：寻找逆序 第 k 个节点：利用快慢指针。

代码如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */classSolution{publicListNodeswapNodes(ListNode head,int k){ListNode newHead =newListNode(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存储着下一个节点的地址）

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */classSolution{publicListNodeswapNodes(ListNode head,int k){ListNode newHead =newListNode(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;}elseif(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;}}