[数据结构与算法]代码随想录算法第四天

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

?

?递归法：

1 找终止条件（递归到链表为空或者链表）

2 找返回值? （返回给上一层递归的值是已经交换完成的子链表）

3 单次过程： 只考虑某一步是怎么完成的，我们假设交换的两个节点分别为head，next，next的应该接受上一级返回的子链表，相当于是一个含三个节点的链表交换前两个节点.

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = head.next;// 存一下第二个节点
        head.next = swapPairs(pre.next); 头节点指向
        pre.next = head;//第二个节点指向头
        return pre;

    }
}

确定返回值，假如3 4交换，应该返回4号节点，（所以调用递归函数，其实就是调用递归的返回值，这个返回值是上一层递归的结果）所以是next节点，单层交换逻辑只看 12 节点

?

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

我的思路：创建虚拟头节点，先统计有多少个节点，让处理倒数第n个节点，那么我们正向处理的就是num - n的节点，最后让节点指向他下下个节点，这里判断是否会有下下个节点，没有返回null就好.?

/**
 * 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) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode count = dummy;
        int num = 0;
        while(count.next!= null){
            count = count.next;
            num++;
        }
        
        ListNode fast = dummy;
        while((num-n) > 0 ){
            fast = fast.next;
            num--;
        }
        if(fast.next.next!= null){
            fast.next = fast.next.next;
        }else{
            fast.next = null;
        }
        return dummy.next;
    }
}

快慢指针法，我让快指针先走n个节点，然后同时向前走到节点为null，这样慢指针所指的节点就是倒数第n个几点，这样删除慢指针所指向的节点就ok了

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        while(n-- > 0) {
            fast = fast.next;
        }
        ListNode prev = dummy;
        while(fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        prev.next = slow.next;
        slow.next = null;
        return dummy.next;
    }
}

面试题 02.07. 链表相交

思路：哈希集合，可以用哈希集合存储链表节点。首先遍历链表A，将链表A节点加入哈希集合，然后遍历链表B,看看B内节点是否在哈希集合中，如果当前节点在哈希集合中，那么后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，返回该节点就好啦，如果B的所有节点不在哈希表中，返回null；

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited= new HashSet<>();
        ListNode temp = headA;
        while(temp !=null){
            visited.add(temp);
            temp = temp.next; 
        }
        temp =headB;
        while(temp!=null){
            if(visited.contains(temp)){
                return temp;
            }
            temp =temp.next;
        }
        return null; 
    }
}

这里需要注意：返回的是相同节点并不是相同的值，这里会产生误区，节点是又有值，又有指针

142. 环形链表 II

?

?数学知识

1. f=2s （快指针每次2步，路程刚好2倍）

2. f = s + nb (相遇时，刚好多走了n圈

推出 s = nb

方法二：快慢指针第一次相遇时，就知道环的长度。然后再让快慢两个指针从头跑，快指针先移动，每次移动环的长度。慢指针每次移动一个。这样相当于慢指针每走一步，快指针就将环走了一遍，相遇的时候就是入口了，这样也是能AC的。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode Index1 = fast;
                ListNode Index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while(Index1!= Index2){
                    Index1 = Index1.next;
                    Index2 = Index2.next;
                }
                return Index1;
            }
        }
        return null;
    }
}