随想录一期 day4 [24. 两两交换链表中的节点|19. 删除链表的倒数第 N 个结点|面试题 02.07. 链表相交|142. 环形链表 II]

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路（遍历）

• 画图分析要交换的节点
• 待交换节点一定有两个节点才能满足交换条件，顾循环条件为pre.next和pre.next.next
• 头结点在第一次循环后，需要指向最新的头结点，然后修改pre引用关系

复杂度

• 时间 O(n)
• 空间 O(1)

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head ; 
        ListNode pre = dummy  ;
        while(pre.next != null && pre.next.next !=null){
           ListNode cur = pre.next ,next =cur.next ;
           cur.next = next.next ; 
           next.next = cur; 
           //原指针指向最新的头节点
           pre.next = next ; 
           //重新给pre引用复制
           pre = cur ;
        }
        return dummy.next; 
    }
}

思路（递归）

• 终止条件，当前节点为空或者下一个节点为空，必须满足有两个节点才能进行顺序交换
• 每次递归交换两个节点顺序，并返回交换后的新节点

复杂度

• 时间 O(n)
• 空间 O(1)

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head ;
        //每次交换两个元素，则新节点的头为当前头的下一个节点
        ListNode newHead = head.next ; 
        //旧节点指向下一个新节点：每迭代一次得到当前节点的下一个新节点（已交换顺序）
        head.next = swapPairs(newHead.next);
        //新节点的下一个节点为旧节点的头
        newHead.next = head ; 
        return newHead ;
    }
}

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思考

• 快慢双指针思想，快指针先走k步后，快慢同步
• 若快指针移动n步后为null时，说明删除的是头结点，即return head.next即可
• pre节点记录要删除的节点的上一个节点

复杂度

• 时间 O(n) （n为索引操作的值）
• 空间 O(1)

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return head;
        ListNode slow = head ,fast = head,pre =null ; 
        while(n-->0){
            fast = fast.next ; 
        }
        if(fast == null) return head.next ;
        while(fast != null){
            pre = slow;
            slow = slow.next ;
            fast = fast.next ; 
        }
        pre.next = slow.next ;

        return head ; 
    }
}

160. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思考

• 暴力解法，使用列表存储两个链表的每个节点，若发现已存在则为相遇第一个节点

复杂度

• 时间 O(n)
• 空间 O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA ==null || headB == null) return null;
        Set<ListNode> sets = new HashSet<>();
        ListNode cur = headA;
        while(cur != null){
            if(sets.contains(cur)){
                return cur ;
            }
            sets.add(cur);
            cur = cur.next ;
        }
        cur = headB ;
        while(cur != null){
            if(sets.contains(cur)){
                return cur ;
            }
            sets.add(cur);
            cur = cur.next ;
        }
        

        return null ;
    }
}

高级解法

• 参考倒数第N个节点，两个指针同时移动，第一个结束时，可以找到两个长度只差，交换指针位置，当两只真相同时，即找到相交节点

• 代码解读：

  • 循环条件A!=B ，第一轮较短的链表先结束，结束后长链表引用赋值给短链表，继续循环N步时，长链表结束，短链表赋值给长链表，即N为两个链表长度之差，先结束的已经又走了N步，此时长短处于同一位置
  • 若有重合节点，则直接返回，若无则最终两节点都为null，结束循环

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA , b = headB ;
        while(a !=b ){
           a = a==null? headB :a.next;
           b = b==null? headA :b.next;
        }
        return a; 
    }
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

思考

• 环形链表解法可想到快慢双指针得到环中相遇节点
  • 相遇节点时，slow走的步数和fast走的步数一定是环形节点数量的整数倍nK
  • 所以找到任意一个相遇节点C距离首节点的步数一定为K的倍数，此时从头结点出发T，以相同步伐和C相遇时，即为链表入口节点
• 核心思想：环形链表中节点的数量为快指针先走的步数，此时同步移动，得到入口节点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode node = getInNodeLoop(head);
        if(node == null){
            return null; 
        }
        ListNode tmp = head ;
        while(tmp != node){
            tmp = tmp.next;
            node = node.next;
        }
        return node ; 

    }
    //快慢指针得到任意相遇节点
    public ListNode getInNodeLoop(ListNode head){
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head.next ,fast=slow.next;
        while(slow != null && fast != null){
            if(slow == fast){
                return slow ;
            }
            slow = slow.next ;
            fast = fast.next ;
            if(fast != null){
                fast = fast.next ; 
            }
        }
        return null;

    }
}

总结

• 链表题型的几种指针
  • 左右同步指针（边向中间靠拢）
  • 同向快慢指针（一般快指针速度为慢指针速度的2倍）
  • 左右同步指针（中间向两边扩散）