链表 - Jason's Universe 🛸

142. 环形链表 II

快慢指针相遇时相差的距离为环的长度

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast,slow;
        fast = slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow  == fast) break;
        }
        if(fast == null || fast.next == null) return null;
        slow = head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

21. 合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head= new ListNode(0),cur = head;
        while(list1!=null && list2!=null){ //注意不是list.next 
            if(list1.val<=list2.val){
                cur.next=list1;
                list1 = list1.next; 
            }
            else{
                cur.next=list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1!=null?list1:list2;  //过于优雅
        return head.next;  
    }
}

什么时候需要用虚拟头结点？我这里总结下：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。

86. 分隔链表

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode p = head;
        ListNode head1=new ListNode(-1),cur1 = head1;
        ListNode head2=new ListNode(-1),cur2 = head2;

        while(p!=null){
            if(p.val>=x){
                cur2.next = p;
                cur2 = cur2.next;
            }
            else{
                cur1.next = p;
                cur1 = cur1.next;
            }
            ListNode temp = p.next;
            p.next = null;
            p=temp;
        } 
        
        cur1.next = head2.next;
        return head1.next;
    }
}

注意：断开原list 如果不断开原链表中的每个节点的 next 指针，那么就会出错，因为结果链表中会包含一个环。
总的来说，如果需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的

23. 合并K个升序链表

class Solution {                                    
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val)); //大小和排序规则
        ListNode dump = new ListNode(-1),p=dump;
        for(ListNode head:lists){
            if(head!=null){
                pq.add(head);
            }
        }

        while(!pq.isEmpty()){
            ListNode temp = pq.poll();
            p.next = temp;
            if(temp.next!=null) pq.add(temp.next);
            p=p.next;
        }

        return dump.next;

    }
}

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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast=head;
        ListNode slow=head;
        for(int i=0;i<n;i++){
            fast=fast.next;
        }
        if(fast==null) return head.next; //删头结点
        while(fast.next!=null){ //因为null无next 所以会报错！
            fast = fast.next;
            slow = slow.next;
        }
        slow.next=slow.next.next;
        return head;
    }
}

考虑头结点若删的是头结点则null.next报错

876. 链表的中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        double count=0;
        while(p.next!=null){
            count++;
            p=p.next;
        }
        count = Math.ceil(count/2);
        while(count>0){
            q=q.next;
            count--;
        }
        return q;
    }
}

160. 相交链表

⭐

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1!=p2){
            if(p1==null) p1=headB;
            else p1=p1.next;
            if(p2==null) p2=headA;
            else p2=p2.next;
        }
        return p1;
    }
}