刷题之旅211004

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //虚拟头指针
        ListNode dump = new ListNode(-1), p = dump;
        ListNode p1 = l1, p2 = l2;

        while(p1!=null && p2!=null){
            if(p1.val <= p2.val){
                p.next = p1;
                p1 = p1.next;
            }
            else{
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if(p1 != null)
            p.next = p1;
        if(p2 != null)
            p.next = p2;
        return dump.next;
    }
}

1、如何快速找到k个节点中最小节点：优先级队列（二叉堆）（最小堆）
2、算法时间复杂度：优先队列小根堆排序时间为logk，故总时间Nlogk

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        //虚拟头结点
        ListNode dump = new ListNode(-1), p = dump;
        //优先级队列，最小堆
        PriorityQueue pq = new PriorityQueue<>(lists.length, (a, b)->(a.val-b.val));
        //将k个链表头结点加入小根堆
        for(ListNode head : lists){
            if(head != null)
                pq.add(head);
        }

        while(!pq.isEmpty()){
            //获取最小节点存入结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if(node.next != null)
                pq.add(node.next);
            p = p.next;
        }

        return dump.next;
    }
}

1、2个节点 一个先走k步，后面2个节点一起走n-k步

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // ListNode p1 = head;
        // ListNode p2 = findFromEnd(head, n+1);
        // p2.next = p2.next.next;
        ListNode dump = new ListNode(-1);
        dump.next = head;
        ListNode x = findFromEnd(dump, n+1);
        x.next = x.next.next;
        return dump.next;
    }

    private ListNode findFromEnd(ListNode head, int k){
        ListNode p1 = head;
        //p1先走k步
        for(int i=0; i 
4、单链表的中间节点（lc876） 
分析 
1、快慢步骤 一个走1步，一个走2步
 
java 
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow=head, fast=head;

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

        return slow;
    }
}
 
5、判断链表是否有环 
分析 
1、使用快慢指针，如果fast=slow 证明有环，fast已经比slow多走一环了
 
java 
boolean hasCycle(ListNode head){
	ListNode fast=head, slow=head;
	while(fast!=null && fast.next!=null){
		slow = slow.next;
		fast = fast.next.next;
		if(fast == slow)
			return true;
	}
	return false;
}
 
升级：判断环的起点 
分析 
1、slow 走了K步， fast走了2K步；设相遇点 距离 环起点为 M步
 那么slow 再从头开始走k-m步； fast 从 相遇点也走k-m步， 最终他们将在环起点相遇。
 
java 
public ListNode detectCycle(ListNode head){
	ListNode slow=head, fast=head;
	while(fast!=null && fast.next!=null){
		slow = slow.next;
		fast = fast.next.next;
		if(slow == fast)
			break;
	}
	if(fast == null || fast.next = null)
		return null;//遇到空指针 说明没有环
	//重新指向头结点
	slow = head;
	while(slow != fast){
		slow = slow.next;
		fast = fast.next;
	}
	return slow;
}
 
6、两个链表是否相交（lc160） 
分析 
1、将两个链表分别拼接 ，然后依次从头访问 若遇到相同节点时，则停止，存在相交。如：
 p1： a s d f g
 p2: x d f g
 p1+p2: a s d f g x d f g
 p2+p1: x d f g a s d f g
 显然倒数第三个d开始是相交的
 
java 
public ListNode getIntersectionNode(ListNode headA, ListNode headB){
	ListNode p1=headA, p2=headB;
	while(p1 != p2){
		//p1走一步，若到A链尾 则转到B
		if(p1 == null) p1 = headB;
		else p1 = p1.next;
		if(p2 = null) p2 = headA;
		else p2 = p2.next;
	}
	return p1;
}