1.删除单链表中的元素
- 1.1 删除排序链表中的重复元素
- 1.2 删除排序链表中的重复元素Ⅱ
- 1.3 移除链表元素
2.反转链表
- 2.1 反转链表
- 2.2 反转链表Ⅱ
3.查找链表中结点
- 3.1 链表的中间结点
- 3.2 链表中倒数第k个节点
4.回文链表
5.相交链表
6.合并链表

知识补充：

递归三要素：

大问题能拆成若干个小问题的解。
拆分后的子问题和原问题除了数据规模不同，思路完全相同。
存在问题的终止条件，不借助任何外部函数的特殊值，直接得出答案。

链表问题三大常用方法：

虚拟头节点法
递归
快慢指针法

1.删除单链表中的元素

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

题目链接： 83.删除链表中的重复元素

题目内容：给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次返回已排序的链表。

示例：
在这里插入图片描述
输入：head = [1,1,2,3,3]
输出：[1,2,3]

解法1：迭代

要找重复元素，这里使用两个引用：prev，cur

base case：若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
当链表长度大于1时，给定一个虚拟头结点，让prev指向虚拟头结点，cur指向后一个节点。判断这两个节点的值是否相同。
若不相同，则prev=prev.next。
若相同，prev.next=cur.next，使prev指向相同元素节点的下一个节点,cur=cur.next，再继续判断，重复以上过程。
最后返回dummyHead.next即可。

在这里插入图片描述

    public ListNode deleteDuplicates(ListNode head) {
        //base case
        if(head==null || head.next==null){
            return head;
        }
        //此时链表一定两个节点
        //虚拟头节点
        ListNode dummyhead=new ListNode(-101);
        dummyhead.next=head;
        //prev指向的一定不是重复元素
        ListNode prev=dummyhead;
        //双指针比较元素是否重复
        ListNode cur=prev.next;
        while(cur!=null){
            if(prev.val==cur.val){
                prev.next=cur.next;
            }else{
                prev=prev.next;
            }
            cur=cur.next;
        }
        return dummyhead.next;
    }

解法2：递归

链表是天然的递归结构。

首先，明确deleteDuplicates()方法的作用是删除所有重复的元素，得到一个所有元素只出现一次的已排序的链表。

那么，整个链表就可以分为 head+除head以外的所有节点
在这里插入图片描述
即head+deleteDuplicates(head.next)
此时deleteDuplicates(head.next)已经是一个没有重复元素的链表，那么只需要判断head和此链表的head的值是否相同。

步骤：

边界条件，若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
要删除重复元素，先把以head.next为头结点的子链表中的所有重复元素删除完。
最后比较head和head.next的值。

    public ListNode deleteDuplicates(ListNode head) {
        //base case
        if(head==null || head.next==null){
            return head;
        }
        head.next=deleteDuplicates(head.next);
        return head.val==head.next.val ? head.next:head;
    }

1.2 删除排序链表中的重复元素Ⅱ

题目链接： 82.删除排序链表中的重复元素Ⅱ

题目内容： 给定一个已排序的链表的头 head ，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。

示例：
在这里插入图片描述
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

本题和上一题不同的地方在于，只留下不同的元素，重复元素一个不留。

解法1：迭代

这里使用三指针法：prev,cur,sec

prev一定指向不同元素
sec一定指定cur的下一个

在这里插入图片描述

步骤：

边界条件，若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
当sec==null时，循环结束，没有可比较的对象了。
当cur.val != sec.val，prev=prev.next，prev向后移动。
当cur.val==sec.val时，循环判断，sec一直向后移动，直到cur.val != sec.val，此时prev.next指向sec。
cur移动到sec的位置。在新一轮循环中，让sec=cur.next。继续判断。

public ListNode deleteDuplicates(ListNode head) {
        //base case
        if(head==null || head.next==null){
            return head;
        }
        //虚拟头结点
        ListNode dummyHead=new ListNode(-101);
        dummyHead.next=head;
        ListNode prev=dummyHead;
        ListNode cur=prev.next;
        while(cur!=null){
            ListNode sec=cur.next;
            if(sec==null){
                break;
            }
            if(cur.val!=sec.val){
                prev=prev.next;
            }else{
                while( sec!=null && cur.val==sec.val){
                    sec=sec.next;
                }
                //此时,sec和cur一定不相等
                prev.next=sec;
            }
            cur=sec;
        }
        return dummyHead.next;
    }

解法2：递归

链表可以看作head以head.next为头结点的子链表的组合。
在这里插入图片描述

思路：

边界条件，若链表为空或只有一个元素，肯定不会有重复元素，直接返回即可。
若head.val !=head.next.val，head.next直接指向以head.next为头结点的链表。
若head.val ==head.next.val，此时头结点就是重复的节点，先处理头结点的情况，给定一个引用newHead等于head.next。判断head.val==newHead.val，若相等，让newHead不停向后移动，直到不相等。此时newHead一定不是重复元素，返回deleteDuplicates(newHead)。

    public ListNode deleteDuplicates(ListNode head) {
        //base case
        if(head==null || head.next==null){
            return head;
        }
        if(head.val !=head.next.val){
            head.next=deleteDuplicates(head.next);
            return head;
        }else{
        	//头结点就是重复的节点，先处理完头结点的情况
            ListNode newHead=head.next;
            while(newHead!=null && head.val==newHead.val){
                newHead=newHead.next;
            }
            //此时newHead一定不是重复元素
            return(deleteDuplicates(newHead));
        }
    }

1.3 移除链表元素

题目链接： 203.移除链表元素

题目内容： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

示例：
在这里插入图片描述
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

解法1：迭代

思路：

边界条件，如何head为空，直接返回null。
给定一个虚拟头结点，连接head。给定一个引用prev指向虚拟头结点。（注意：prev一定指向值不为val的节点）
遍历链表。若prev.next.val==val，prev直接指向prev.next的下一个节点。
若不相等，prev直接向后移动。

		public ListNode removeElements(ListNode head, int val) {
        //1.base case
        if(head==null){
            return null;
        }
        //虚拟头节点
        ListNode dummyHead=new ListNode();
        dummyHead.next=head;
        //prev一定指向值不为val的节点
        ListNode prev=dummyHead;
        while(prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else{
                prev=prev.next;
            }
        }
        return dummyHead.next;
    }

解法2：递归

链表可以看作head以head.next为头结点的子链表的组合。
在这里插入图片描述

思路：

边界条件，如何head为空，直接返回null。
removeElements(head.next,val)一定是值不为val的链表。head.next直接指向removeElements(head.next,val)。
此时只需判断头节点的值是否为val。若是，返回head.next，否则返回head。

    public ListNode removeElements(ListNode head, int val) {
        //base case
        if(head==null){
            return null;
        }
        head.next=removeElements(head.next,val);
        return head.val==val ? head.next:head;
    }

2.反转链表

2.1 反转链表

题目链接：206.反转链表

题目内容： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：
在这里插入图片描述
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解法1：头插法

思路：若题目没有空间限制，则可以遍历原链表，不断产生新节点，在头插到新链表中，最后返回新链表。

   public ListNode reverseList(ListNode head) {
        //base case 
        if(head==null || head.next==null){
            return head;
        }
        //虚拟头结点
        ListNode dummyHead=new ListNode(-1);
        //不断遍历原链表，产生新节点，头插到新链表
        while(head!=null){
            ListNode cur=new ListNode(head.val);
            cur.next=dummyHead.next;
            dummyHead.next=cur;
            head=head.next;
        }
        return dummyHead.next;
    }

解法2：原地反转

思路：

原先prev是指向cur的，反过来，让cur指向prev就实现了反转。
但是cur.next指向prev之后，剩下的链表就断开了找不到了，所以需要先用一个next记住原链表cur的下一个节点。
当cur为null时，prev刚好在最后一个节点，直接返回prev即可。

在这里插入图片描述

    public ListNode reverseList(ListNode head) {
        //base case
        if(head==null || head.next==null){
            return null;
        }
        ListNode prev=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }

解法3：递归

思路：

reverseList(ListNode head)的作用是得到一个反转后的链表。

则可以把链表分为头节点和以head.next为头节点的反转后的链表。

此时只需要将head连接到子链表的尾端即可。

在这里插入图片描述

    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode next=head.next;
        ListNode newHead=reverseList(head.next);
        //拼接当前头节点和转后的子链表
        head.next=null;
        next.next=head;
        return newHead;
    }

2.2 反转链表Ⅱ

题目链接：92.反转链表Ⅱ

解法：

思路：

给定两个引用，记住left的前一个节点和right的后一个节点。
先将待反转的区域反转
把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。

在这里插入图片描述

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //base case
        if(head==null || head.next==null){
            return head;
        }
        ListNode dummyHead=new ListNode(-1);
        dummyHead.next=head;
        
        ListNode prev=dummyHead;
        //从temp开始走，来到left的前一个节点
        for(int i=0;i<left-1;i++){
            prev=prev.next;
        }
        //从prev开始走，一直到right节点
        ListNode rightNode=prev;
        for(int i=0;i<right-left+1;i++){
            rightNode=rightNode.next;
        }
        
        //截取要反转的链表
        ListNode next=rightNode.next;
        ListNode leftNode=prev.next;
        //切断连接
        prev.next=null;
        rightNode.next=null;

        //反转链表子区间
        reverseList(leftNode);

        //接回原链表
        prev.next=rightNode;
        leftNode.next=next;
        return dummyHead.next;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }

3.查找链表中结点

3.1 链表的中间结点

题目链接：876.链表的中间结点

题目内容： 给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例：
在这里插入图片描述
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

解法1：按长度查找

步骤：

遍历原链表，得到链表的长度
若长度为奇数，直接走长度/2 的步数。
若长度为偶数，也是直接走长度/2 的步数。

    public ListNode middleNode(ListNode head) {
        int count=0;
        ListNode temp=head;
        while(temp!=null){
            temp=temp.next;
            count++;
        }
        int n=count/2;
        while(n>0){
            head=head.next;
            n--;
        }
        return head;
    }

解法2：快慢指针法

思路：

两个指针,low 和 fast
low每走一步，fast就走两步
当fast走到终点，low就停在我们想要的位置

在这里插入图片描述

    public ListNode middleNode(ListNode head) {
        ListNode low=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            low=low.next;
            fast=fast.next.next;
        }
        return low;
    }

3.2 链表中倒数第k个节点

题目链接：剑指Offer 22.链表中倒数第k个结点

题目内容： 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解法1：按长度查找

思路：

遍历链表，得到链表的长度n。
倒数第k个结点就是正数第n-k个结点。

    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null || k<=0){
            return null;
        }
        ListNode temp=head;
        int n=0;
        while(temp!=null){
            temp=temp.next;
            n++;
        }
        int count=n-k;
        while(count>0){
            head=head.next;
            count--;
        }
        return head;
    }

解法2：快慢指针法

思路：

给定两个引用sec，fir
fir先向前走k步。
sec 和 fir 同时向前走，当fir为null时，sec刚好指向倒数dik个结点。

在这里插入图片描述

    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null || k<=0){
            return null;
        }
        ListNode fir=head;
        ListNode sec=head;
        for(int i=0;i<k;i++){
            //判断k>链表长度的情况
            if(fir==null){
                return null;
            }
            fir=fir.next;
        }
        while(fir!=null){
            fir=fir.next;
            sec=sec.next;
        }
        return sec;
    }

4.回文链表

题目链接：234.回文链表

题目内容： 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例：
在这里插入图片描述
输入：head = [1,2,2,1]
输出：true

解法

思路：

判断回文链表其实就是判断对称链表。
将链表一份为二，l1为头节点到中间结点的链表，l2为中间结点到尾节点的链表。
将l2反转，与l1的值进行对比。遍历，直到其中一条链表走到null，若有不一样的值，则不为回文链表。反之，则是回文链表。

在这里插入图片描述

   public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null){
            return true;
        }
        ListNode middleNode=middleNode(head);
        //反转中间结点之后的链表
        ListNode l2=reverseList(middleNode);
        //找反例
        while(head!=null && l2!=null){
            if(head.val != l2.val){
                return false;
            }
            head=head.next;
            l2=l2.next;
        }
        return true;
    }
    //查找中间节点
    public ListNode middleNode(ListNode head) {
        int count=0;
        ListNode temp=head;
        while(temp!=null){
            temp=temp.next;
            count++;
        }
        int n=count/2;
        while(n>0){
            head=head.next;
            n--;
        }
        return head;
    }
    //反转链表
      public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode next=head.next;
        ListNode newHead=reverseList(head.next);
        //拼接当前头节点和转后的子链表
        head.next=null;
        next.next=head;
        return newHead;
    }

5.相交链表

题目链接：160.相交链表

题目内容： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

示例：
在这里插入图片描述
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

解法：

如图所示：

listA的长度=x+z
listB的长度=y+z

但若让A和B都走一遍对方的路程：即 x+z+y=y+z+x。此时它们的路程一定相等，走完之后一定会相交。

在这里插入图片描述
过程图举例：

步骤：

引入两个引用listA，listB。
listA走到终点后倒过来走listB。
listB走到终点后倒过来走listA。
若不存在交点，则listA和listB最后都指向null。
若存在交点，则两个链表走完全程后一定指向交点。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //引入两个引用
        ListNode listA=headA;
        ListNode listB=headB;

        while(listA!=listB){
            listA = listA==null ? headB:listA.next;
            listB = listB==null ? headA:listB.next;
        }
        return listA;
    }

6.合并链表

题目链接：21.合并两个有序链表

题目内容： 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
在这里插入图片描述
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

解法1：虚拟头节点法

思路：

给定一个虚拟头结点dummyHead；
遍历两个链表。比较结点值的大小，将较小值拼接在新链表后面。

图解：

在这里插入图片描述

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode dummyHead=new ListNode(-1);
        ListNode tail=dummyHead;
        //取较小值拼接在链表的尾部
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                tail.next=list1;
                tail=list1;
                list1=list1.next;
            }else{
                tail.next=list2;
                tail=list2;
                list2=list2.next;
            }
        }
        //此时，至少一个链表为Null
        if(list1==null){
            tail.next=list2;
        }
        if(list2==null){
            tail.next=list1;
        }
        return dummyHead.next;
    }

解法2：递归

思路：

已知 mergeTwoLists(ListNode list1, ListNode list2)方法的作用是将两个升序链表合并为一个新的升序链表并返回。
如果list1.val<list2.val，此题可以看作list1+ mergeTwoLists(ListNode list1.next, ListNode list2)
如果list2.val<list1.val，此题可以看作list2+ mergeTwoLists(ListNode list1, ListNode list2.next)

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        if(list1.val<=list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }