链表训练

21. 合并两个有序链表

//迭代做法
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy=new ListNode();//创建1个虚拟节点 方便后面操作
        ListNode head=dummy;
        while(l1!=null&&l2!=null)
        {
            if(l1.val<l2.val)
            {
                head.next=l1;
                l1=l1.next;
                head=head.next;
            }
            else
            {
                head.next=l2;
                l2=l2.next;
                head=head.next;
            }
        }
        if(l1!=null)
            head.next=l1;
        if(l2!=null)
            head.next=l2;
        return dummy.next;
    }
}
//O(m+n) m,n分别是l1 l2的节点数目
//O(1)

//递归做法
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        else if(l2==null)
            return l1;
        else if(l1.val<l2.val)
        {
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
        else
        {
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }

    }
}
//O(m+n) m,n分别是l1 l2的节点数目
//O(m+n)

23. 合并K个升序链表

和合并两个升序链表的题目类似，这里主要的问题就是如何获得当前的K条链表中的K个头节点中的最小值，因为每一条链表都是升序的，因此每条链表的最小值一定是头节点 可以实验一个优先级队列（小顶堆，降序）加入K条链表的头节点，这样poll出来的就是当前的最小头节点 设链表有K条， 链表的节点总数是N 时间复杂度： 每次poll复杂度O(logK) 一共N次 所以O(NlogK) 空间复杂度：O(k) 优先级队列中最多存储K个节点

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq=new PriorityQueue<>(
            new Comparator<ListNode>()
            {
                public int compare(ListNode node1,ListNode node2)
                {
                    return node1.val-node2.val;
                }

            }
        );
        for(ListNode head:lists)
           if(head!=null)
                pq.offer(head);
        ListNode dummy=new ListNode();
        ListNode pre=dummy;
        while(!pq.isEmpty())
        {
            ListNode node=pq.poll();
            pre.next=node;
            pre=pre.next;
            if(node.next!=null)
                pq.offer(node.next);
        }
        return dummy.next;

    }
}

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

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

        ListNode dummy=new ListNode();//加入虚拟节点 统一操作 不用单独考虑删除头节点的情况
        dummy.next=head;
        ListNode slow=dummy,fast=dummy;
        for(int i=0;i<=n;i++)//移动n+1步 因为加入了虚拟节点
            fast=fast.next;
        while(fast!=null)//找到倒数第n+1个节点 即待删除节点的前一个节点
        {
            fast=fast.next;
            slow=slow.next;
        }

        slow.next=slow.next.next;
        return dummy.next;

    }
}
//O(n)
//O(1)

876. 链表的中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow=head,fast=head;//初始时快慢指针都指向头节点
        //快指针每次比慢指针多走1步 由于偶数节点是 返回中间的第2个节点 
        //代码可以将两种情况统一
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;//slow指向中间节点

    }
}
//O(n)
//O(1)

141. 环形链表

思路1：实验set, 反复地添加节点，如果添加失败（遇到相同的节点）则说明有环，返回true 思路2：快慢指针，和前面一题代码类似，fast每次比slow多走一步，如果二者相遇说明有环，否则没有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set=new HashSet<>();
        while(head!=null)
        {
            if(!set.add(head))
                return true;
            head=head.next;
        }
        return false;

    }
}
//O(n)
//O(n)

public class Solution {
    public boolean hasCycle(ListNode head) {

        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast)
                return true;
        }
        return false;

    }
}
//O(n)
//O(1)

142. 环形链表 II

这一题不仅要求判断是否有环，还要直到环的入口在哪，参考下图，当slow和fast相遇时，设slow走了k步，则fast走了2k步，其中多走的k步其实就是环的长度，fast指针和slow指针相遇时fast指针只多走了1圈，因为fast的速度是slow的两倍

假设环起点和相遇点距离为m, 则出发点巨鹿环起点距离是k-m 由于1圈的长度是k 因此相遇点到环起点的长度也是k-m, 因此相遇之后，slow从起点出发，fast从相遇点出发，此时二者速度相同，再次相遇的点就是环的入口点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast)
                break;
        }
        //如果fast满足这两个条件 说明没有环
        if(fast==null||fast.next==null)
            return null;
        slow=head;
        while(slow!=fast)
        {
            slow=slow.next;
            fast=fast.next;
        }
        return slow;

    }
}
//O(n)
//O(1)

160. 相交链表

1. 如果两条链表没有交点，如示例3，则当p1==p2==null时循环结束，返回p1即返回null
2. 如果两条链表有交点，记录公共部分的交点数目为x, A链表的节点数目是a, B链表的节点数目是b,

2.1 如果a==b 则p1走了a-x步 p2走了b-x步 a-x==b-x 没有走完直接相遇 2.2 如果a!=b 则p1走到交点处走了a+(b-x)步 p2走到交点处走了b+(a-x)步 二者也相等，也会相遇 也就是说p1 p2最多走a+b-x步就会相遇

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

    }
}
//O(n)
//O(1)

206. 反转链表

思路1: 迭代 需要使用3个变量 pre cur next pre初始化为null,cur初始化为head 反转后的头节点就是pre

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null,cur=head,next;
        while(cur!=null)
        {
            next=cur.next;//next保存下一个节点的引用
            cur.next=pre;//当前节点的指针指向前一个节点  第一次指向null
            pre=cur;//当前节点变成前一个节点
            cur=next;//下一个节点变成当前节点
        }
        return pre;
    }
}
//O(n)
//O(1)

思路2： 递归

class Solution {
    public ListNode reverseList(ListNode head) {
         if(head==null||head.next==null)//当前节点为空或者只有1个节点直接返回
            return head;
        ListNode newHead=reverseList(head.next);//反转剩下的n-1个节点
        head.next.next=head;//假设head后面的节点已经反转完成 head的下一个节点应该指向head自己
        head.next=null;//head自己指向null
        return newHead;//返回新的头节点
    }
}
//O(n)
//O(n)

92. 反转链表 II

思路1： 迭代 两遍扫描链表，先找到开始节点，再找到结束节点，然后按照上面一题的反准思路进行反转，反转完成以后需要改变区第left-1个节点和第left个节点的指向

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;
        for(int i=1;i<left;i++)
        {
            pre=pre.next;//pre指向第left-1个节点
        }

        ListNode tail=pre.next;
        for(int i=left;i<=right;i++)
        {
            tail=tail.next;//tail指向第right+1个节点  在图中是节点5
        }
       ListNode pre2=null,cur=pre.next,next=null;
       //和普通的单链表反转类似 pre2最终指向反转后的头节点  在图中是节点4
       for(int i=left;i<=right;i++)
       {
           next=cur.next;
           cur.next=pre2;
           pre2=cur;
           cur=next;
       }
       //pre.next指向第left个节点  在图中即最后需要4-->5
       pre.next.next=tail;
       //pre指向反转后的头节点 在图中即1-->4
       pre.next=pre2;
       return dummy.next;

    }
}
//O(n)
//O(1)

思路2： 一遍扫描，只需要找出反转区间的开始节点，不用找出结束节点

分为3个步骤：

1. 当前节点指向下下一个节点
2. 下一个节点指向当前节点
3. 前一个节点指向下一个节点

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode pre=dummy;
        for(int i=1;i<left;i++)
        {
            pre=pre.next;//pre指向第left-1个节点
        }
       ListNode cur=pre.next,next;
       for(int i=left;i<right;i++)
       {
           next=cur.next;
           cur.next=next.next;//当前节点指向下下一个节点
           next.next=pre.next;//下一个节点指向当前节点
           pre.next=next;//前一个节点指向下一个节点
       }
       return dummy.next;

    }
}
//O(n)
//O(1)

递归： 先定义一个函数：reverseN(head,n) 用来反转链表的前n个节点 即反转区间为[1,n] 而对于题目要求的是区间[left,right] 如何将left转化为1？ 依据相对性，left对于head而言是第left, 而对于head.next而言则是第left-1, 对于head.next.next而言是left-2…. 依次类推，最终会得到left==1, 此时转化为反转区间[1-n]个节点， 对于反转reverseN(head,n)继续递归划分reverseN(head.next,n-1) 假设后面head.next后面的都反转好了，只需要改变head的指向和head.next的指向即可

class Solution {
    ListNode suc;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==1)
        {
            return reverseN(head,right);
        }
        head.next=reverseBetween(head.next,left-1,right-1);
        return head;

    }
    public ListNode reverseN(ListNode head,int n)
    {
        if(n==1)
        {
            suc=head.next;//记录反转区间结束的下一个节点 当n==链表结点数时 suc=null 变成了普通的单链表反转
            return head;
        }
        ListNode newHead=reverseN(head.next,n-1);
        head.next.next=head;
        head.next=suc;//全部反转时这里是head.next=null  由于这里是部分反转因此需要指向后继节点
        return newHead;
    }

}
//O(n)
//O(n)