LeetCode：链表

160. 相交链表

/**
 * 单链表的定义
 * 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) {
        ListNode l1 = headA;
        ListNode l2 = headB;

        while(l1 != l2){
            if(l1!=null){
                l1=l1.next; //指针移动到下一个节点
            }else{
                l1=headB;//指针移动到最后，换成另一个链表遍历
            }

            if(l2!=null){
                l2=l2.next;
            }else{
                l2=headA;
            }
        }
        return l2;

    }
}

206. 反转链表

讲解：反转链表【基础算法精讲 06】_哔哩哔哩_bilibili

/**
 * 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 reverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;

        //原地调整链表
        //利用cur、nxt、pre三个新指针
        ListNode cur = head;
        ListNode pre = null;

        while(cur!=null){
            //nxt指针为当前节点的下一个
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

21. 合并两个有序链表

【从零开始刷LeetCode】第四天：合并两个有序链表（动画演示、手写 Java 代码、详细注释、LeetCode 高频算法题）_哔哩哔哩_bilibili

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;

        //虚拟头节点
        ListNode dummy = new ListNode(-1);
        //虚拟前置指针
        ListNode pre = dummy;

        while(list1!=null && list2!=null){
            if(list1.val <= list2.val){
                pre.next = list1;
                list1=list1.next;
            }else{
                pre.next = list2;
                list2=list2.next;
            }
            pre = pre.next;
        }

        //以防一个链遍历完了，另一个没有遍历完
        if(list1==null && list2!=null)
            pre.next=list2;
        if(list1!=null && list2==null)
            pre.next=list1;
        
        return dummy.next;
    }
}

83. 删除排序链表中的重复元素

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        ListNode pre = new ListNode(-1);

        pre = head;

        while(cur!=null && cur.next!=null){
            if(cur.val==cur.next.val){
                pre=cur;
                cur.next=cur.next.next;
            }else{
                pre=cur;
                cur=cur.next;
            }
        }

        return head;
    }
}

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode cur = head;
        ListNode dummy = head;
        int len=0;

        while(cur!=null){
            cur=cur.next;
            len++;
        }

        ListNode newCur = head;

        for(int i=0; i<len-n-1; i++){
            newCur=newCur.next;
        }

        newCur.next=newCur.next.next;

        return dummy;
        
    }
}
删除链表的倒数第N个节点这道题中，我写的newCur.next=newCur.next.next;
这一句为什么报错？

在您提供的代码中，报错的原因可能是因为当您试图删除倒数第N个节点时，
如果N等于链表的长度（即要删除的是头节点），
那么在执行 newCur.next = newCur.next.next; 这一行时，
newCur 实际上可能是 null，因为 len - n - 1 可能为 -1。

为了修复这个问题，您应该修改循环条件，并确保在删除节点之前 newCur 不是 null。
以下是修改后的代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = head;
        
        int len = 0;

        // 计算链表长度
        while (cur != null) {
            cur = cur.next;
            len++;
        }

        
        ListNode dummy = new ListNode(0); // 创建一个哑节点，指向头节点
        dummy.next = head;

//头节点可能会被删除，所有用一个dummy作为head的替身，最后返回的不是head，而是dummy.next
        ListNode newCur = dummy; // 从哑节点开始遍历

        // 找到要删除节点的前一个节点
        for (int i = 0; i < len - n; i++) {
            newCur = newCur.next;
        }

        // 删除节点
        newCur.next = newCur.next.next;

        return dummy.next; // 返回哑节点的下一个节点，即新的头节点
    }
}
创建了一个哑节点 dummy，它的 next 指向 head。这样即使删除的是头节点，我们也可以通过 dummy 正确地返回新的头节点。
循环条件从 len - n - 1 改为 len - n，因为我们要找到要删除节点的前一个节点。
返回值从 dummy 改为 dummy.next，这样即使头节点被删除，也能正确返回新的头节点。

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

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;

//pre的位置选取是待处理两个节点的前一个
//l1、l2都是在循环里设的
//熟悉过程
        while(pre.next!=null && pre.next.next!=null){
            ListNode l1 = pre.next;
            ListNode l2 = pre.next.next;
            ListNode nxt = l2.next;

            pre.next=l2;
            l2.next=l1;
            l1.next=nxt;
            pre=l1;

        }

        return dummy.next;
    }
}

234. 回文链表

class Solution {
    public boolean isPalindrome(ListNode head) {

        ListNode mid = findMiddle(head);
        ListNode list2 = reverseList(mid);


        while(list2!=null){
            if(head.val != list2.val){
                return false;
            }
            head=head.next;
            list2=list2.next;                
        }

        return true;

    }


    //快慢指针找中点
    public ListNode findMiddle(ListNode head){

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow=slow.next;
            fast=fast.next.next;
        }

        return slow;
    }


    //还是反转链表
    public ListNode reverseList(ListNode head){

        if(head==null || head.next==null)
            return head;

        ListNode pre = null;
        ListNode cur = head;

        while(cur!=null){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

}

141. 环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null || head.next==null)
            return false;

        ListNode slow = head;
        ListNode fast = head;

//存在fast.next.next这种越级调用时，需要确保fast.next不为空
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;

            if(slow==fast)
                return true;                       
        }

        return false;
        
    }
}

142. 环形链表 II

public class Solution {
    public ListNode detectCycle(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        while(true){

            if(fast==null || fast.next==null) return null;

            slow=slow.next;
            fast=fast.next.next;

            //定位到两针相遇位置,跳出，此时确定有环
            if(slow==fast)
                break;
        }
        
        //此时从head处走到环的开始处 与 从相遇处走到环的开始处 步数一样
        fast=head;

        while(fast!=slow){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
        
    }
}

725. 分隔链表

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {

        ListNode[] ans = new ListNode[k];

        if(head==null) return ans;

        // 遍历链表
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }

        // 计算每组的长度 和 多余的长度
        int subLen = (len>k) ? (len/k):1;
        int rest = (len>k) ? (len%k):0;

        cur = head;
        int num = 0;
        while(cur!=null){
            //每组需要移动的长度
            int move = subLen + (((rest--)>0)?1:0);
            for(int i=0; i<move-1; i++){
                cur=cur.next;
            }

            ans[num]=head;
            head=cur.next;
            cur.next=null;
            cur=head;
            num++;
        }

        return ans;
    }
}

148. 排序链表

【力扣hot100】【LeetCode 148】排序链表｜归并排序的应用_哔哩哔哩_bilibili

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null) return head;
        
        ListNode head2 = middleList(head);
        
        head = sortList(head);
        head2 = sortList(head2);

        return merge(head, head2);
    }


//找链表中点，并断链
    public ListNode middleList(ListNode head){
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;

        ListNode slow = head;
        ListNode fast = head;

        while(fast!=null && fast.next!=null){
            //pre=pre.next 不行，有空指针
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;

        return slow;
    }


//两个链表合成有序链表
    public ListNode merge(ListNode list1, ListNode list2){
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }

        //以防有链表没结束
        if(list1!=null && list2==null) cur.next=list1;
        if(list1==null && list2!=null) cur.next=list2;

        return dummy.next;

    }
}

138. 随机链表的复制

题解：leetcode上——> 两种实现+图解 138. 复制带随机指针的链

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return head;

        Node pre = head;
        
//在每个节点后面设置新节点
        while(pre!=null){
            Node newNode = new Node(pre.val, pre.next, null);
            pre.next=newNode;
            pre=newNode.next;
        }

        pre=head;
//设置新节点的随机random指针
        while(pre!=null && pre.next!=null){
            if(pre.random!=null)
                pre.next.random=pre.random.next;

            pre=pre.next.next;
        }

        Node cur = head;

        Node dummy = new Node(-1);
        pre=dummy;

//设法将新旧两个链表分开
        while(cur!=null){
            pre.next=cur.next;
            pre=pre.next;

            cur.next=pre.next;
            cur=cur.next;           
        }

        return dummy.next;
    }
}

146. LRU 缓存

class LRUCache {

    private static class Node {
        Node pre, next;
        int key, value;

        // 构造器
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Node dummy = new Node(0, 0);
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.next = dummy;
        dummy.pre = dummy;
    }

    public int get(int key) {
        Node node = getAndFront(key);
        if (node == null) {
            return -1;
        }
        return node.value;
    }

    //易错处
    public void put(int key, int value) {
        // 如果key的node存在
        Node node = keyToNode.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            addFront(node);
            return;
        }

        // 这个key不存在，新建node
        node = new Node(key, value);
        addFront(node);
        keyToNode.put(key, node);
        if (keyToNode.size() > capacity) {
            // 从表尾删除一个节点
            Node lastNode = dummy.pre;
            keyToNode.remove(lastNode.key);
            remove(lastNode);
        }

    }

    // 以上的put和get应基于以下几个基础操作
    // 删除节点
    public void remove(Node x) {
        x.pre.next = x.next;
        x.next.pre = x.pre;
    }

    // 从链表头插入
    public void addFront(Node x) {
        x.pre = dummy;
        dummy.next.pre = x;
        x.next = dummy.next;
        dummy.next = x;
    }

    // 用key get某个节点，并把节点移到链表头部
    public Node getAndFront(int key) {
        if (!keyToNode.containsKey(key))
            return null;

        Node node = keyToNode.get(key);
        remove(node);
        addFront(node);
        return node;
    }
}

2. 两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 辅助节点
        ListNode pre = dummy;
        
        //进位carry
        int carry=0;

        while(l1!=null || l2!=null){
            if(l1!=null){
                carry += l1.val;
                l1=l1.next;
            }
            if(l2!=null){
                carry += l2.val;
                l2=l2.next;
            }

            //新节点是carry的个位数
            pre.next = new ListNode(carry%10);
            pre = pre.next;
            
            //判断是否有进位
            carry = (carry>=10)?1:0;
        }

        //最后循环结束，如果有进位，还需要补上最后一个1（这个1是最高位的1）
        if(carry==1){
            pre.next = new ListNode(carry);
        }

        return dummy.next;
    }
}

25. K 个一组翻转链表(⭐)

【LeetCode 每日一题】25. K 个一组翻转链表 | 手写图解版思路 + 代码讲解_哔哩哔哩_bilibili

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode dummy = new ListNode(-1, head);


        ListNode start_pre = dummy;
        ListNode end = dummy;

        while(true){
            //遍历end，至本组最后一个节点
            for(int i=0; i<k&&end!=null; i++)
                end=end.next;
            if(end==null) break;

            //start为本组第一个节点
            ListNode start = start_pre.next;

            //endNxt为下一组的最后一个节点
            ListNode endNxt = end.next;

            //翻转之前把链断掉
            end.next=null;

            //翻转本组节点
            start_pre.next = reverse(start);

            //翻转之后，本组的尾部去接下一组的头部
            start.next=endNxt;

            //调整各个指针位置
            end = start;
            start_pre = start;
        }

        return dummy.next;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;

        while(cur!=null){
            ListNode nxt = cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }

        return pre;
    }
}

23. 合并 K 个升序链表（hard）

迭代法

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) return null;
        
        while(n>1){
            //index每次都初始化为0，因为要在lists的开头来存放合并出来的临时结果
            int index = 0;
            for(int i=0; i<n; i+=2){

                ListNode l1 = lists[i];
                ListNode l2 = null;
                if(i+1<n)
                    l2 = lists[i+1];

                lists[index++] = mergeTwoLists(l1, l2);
            }
            //index是lists数组新的长度
            n = index;
        }
        return lists[0];
    }

递归法

/**
 * 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 mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        
        return merge(lists, 0, lists.length-1);
    }


    //递归法
    public ListNode merge(ListNode[] lists, int low, int high){
        if(low==high)
            return lists[low];

        int middle = low + (high-low)/2;
        ListNode l1 = merge(lists, low, middle);
        ListNode l2 = merge(lists, middle+1, high);

        return mergeTwoLists(l1, l2);
    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null)
            return null;
        if (list1 == null || list2 == null)
            return (list1 == null) ? list2 : list1;

        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                pre.next = list1;
                list1 = list1.next;
            } else {
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }

        if (list1 != null)
            pre.next = list1;
        if (list2 != null)
            pre.next = list2;

        return dummy.next;
    }
}