链表专题 - 《leetcode刷题》

LeetCode 19. Remove Nth Node From End of List 2:30
LeetCode 237. Delete Node in a Linked List 14:30
LeetCode 83. Remove Duplicates from Sorted List 22:08
LeetCode 61. Rotate List 32:00
LeetCode 24. Swap Nodes in Pairs 44:30
LeetCode 206. Reverse Linked List 53:10
LeetCode 92. Reverse Linked List II 64:00
LeetCode 160. Intersection of Two Linked Lists 77:08
LeetCode 142. Linked List Cycle II 88:15
LeetCode 148. Sort List 101:05
视频地址:https://www.bilibili.com/video/BV1jt411J7tC

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

示例 1：
链表专题 - 图1
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode dummy =new ListNode(-1,head);//构造带头指针的头结点
        ListNode first=head,second=dummy;//用双指针
        //ListNode first=dummy,second=dummy;
        //first为dummy时，下面判断为first.next!=null，否则为first!=null
        while(n>0){
             first=first.next;//遍历到第n+1个结点
             n--;
        }
        //while(first.next!=null)
        while(first!=null){
            first=first.next;//first遍历到最后
            second=second.next;//second遍历到要删除的结点的前一个
        }
        second.next=second.next.next;//删除掉要删除的结点
        return dummy.next;
    }
}

方法1：ListNode first=head,second=dummy;//用双指针

方法2：ListNode first=dummy,second=dummy;

237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 — head = [4,5,1,9]，它可以表示为:
链表专题 - 图5

示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val =node.next.val;
        node.next=node.next.next;//用下一个结点替换就行
    }
}

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2

示例 2:
输入: 1->1->2->3->3
输出: 1->2->3


class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode p=head;
        while(p!=null){
            //判断是否和下一个结点值相同，相同就删除，不相同或者到了最后就到下一个节点
            if(p.next!=null&&p.next.val==p.val)
                p.next=p.next.next;
            else p=p.next;
        }
        return head;
    }
}

61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

 * 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 rotateRight(ListNode head, int k) {
        if(head==null) return null;
        ListNode first=head,second=head;//设置位置，后来最后判断要到first.next
        ListNode cur=head;
        int n=0;//求出链表长度n
        while(cur!=null){
            cur=cur.next;
            n++;
        }
        k=k%n;//取余防止过长
        while(k>0){
            first=first.next;
            k--;//将first先向后移动k位，让first和second保持k位置差距
        }
        while(first.next!=null){
            first=first.next;
            second=second.next;和第一题一样
        }
        first.next=head;
        head=second.next;//这步要在下步前
        second.next=null;
        return head;
    }
}

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：
链表专题 - 图7
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：
输入：head = []
输出：[]

示例 3：
输入：head = [1]
输出：[1]

/**
 * 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 swapPairs(ListNode head) {
        ListNode dummy =new ListNode(-1,head);
        for(ListNode p=dummy;p.next!=null&&p.next.next!=null;){
        ListNode a=p.next,b=a.next;
        p.next=b;//(1
        a.next=b.next;//(2
        b.next=a;//(3
        // p=p.next.next;一样的
        p=a;//(4
        }
        return dummy.next;
    }
}

206. 反转链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null) return null;
        ListNode a=head,b=head.next;
        while(b!=null){
            ListNode c=b.next;
            b.next=a;
            a=b;b=c;
        }
        head.next=null;
        return a;
    }
}

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null) return null;
        ListNode dummy=new ListNode(-1,head);
        ListNode a=dummy,d=dummy;
        if(m==n) return head;
        for(int i=0;i<m-1;i++) a=a.next;
        for(int i=0;i<n;i++) d=d.next;
        //我的版本：
        // ListNode b=a.next,q=b,c=d.next,p=b.next;
        // while(p!=c){
        //     ListNode o=p.next;
        //     p.next=b;
        //     b=p;p=o;
        // }
        // a.next=d;
        // q.next=c;
        //原始版本：
        ListNode b=a.next,c=d.next;
        for(ListNode p=b,q=b.next;q!=c;){//步骤1，和上题一样
            ListNode o=q.next;
            q.next=p;
            p=q;q=o;
        }
        //步骤2
        b.next=c;
        a.next=d;
        return dummy.next;
    }
}

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

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

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
链表专题 - 图17
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
链表专题 - 图18
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

此题还可以用hash

public class Solution {
    public ListNode detectCycle(ListNode head) {
       ListNode fast=head,slow=head;
       while(fast!=null){
           fast=fast.next;
           slow=slow.next;
           if(fast!=null) fast=fast.next;//走两步
           else break;
           if(fast==slow){
               fast=head;//回到起始位置，一次走一步。
               while(fast!=slow){
                   fast=fast.next;
                   slow=slow.next;
               }
               return fast;//两个相遇返回
           }
       } 
       return null;
    }
}

用hashset的做法

public class Solution {
    public ListNode detectCycle(ListNode head) {
       Set<ListNode> hs=new HashSet<ListNode>();
       while(head!=null){
           if(!hs.add(head))
           return head;
           head=head.next;
       }
       return null;
    }
}

148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。
进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
链表专题 - 图22
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode dummy=new ListNode(-1,head);
        int n=0;
        for(ListNode p=head;p!=null;p=p.next) n++;

        for(int i=1;i<n;i*=2){
             ListNode cur=dummy;
             for(int j=0;j+i<n;j+=i*2){
                 ListNode left=cur.next,right=cur.next;
                 for(int k=0;k<i;k++) right=right.next;
                 int l=0,r=0;
                 while(l<i&&r<i&&right!=null)
                    if(left.val<=right.val){
                        cur.next=left;
                        cur=left;
                        left=left.next;
                        l++;
                    }else{
                        cur.next=right;
                        cur=right;
                        right=right.next;
                        r++;
                    }
                    while(l<i){
                         cur.next=left;
                        cur=left;
                        left=left.next;
                        l++;
                    }
                    while(r<i&&right!=null){
                        cur.next=right;
                        cur=right;
                        right=right.next;
                        r++;
                    }
                    cur.next=right;
             }
        }
        return dummy.next;
    }
}

下面是详细解释c++版本的

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //很不熟练，利用自底向上的归并思想，每次先归并好其中一小段，之后对两小段之间进行归并
        int n = 0;
        for(auto p = head; p ; p = p->next) n ++;

        auto dummy = new ListNode(-1);
        dummy->next = head;

        for(int i = 1; i < n; i *= 2 ){ //每次归并段的长度，每次长度依次为1,2,4,8...n/2
        //小于n是因为等于n时说明所有元素均归并完毕，大于n时同理
            auto cur = dummy;
            for(int j = 1;j + i <= n; j += 2 * i){//j代表每一段的开始，每次将两段有序段归并为一个大的有序段，故而每次+2i
            //必须保证每段中间序号是小于链表长度的，显然，如果大于表长，就没有元素可以归并了
                auto p = cur->next,q = p;//p表示第一段的起始点，q表示第二段的起始点，之后开始归并即可
                for(int k = 0; k < i; k ++) q = q->next;

                //x,y用于计数第一段和第二段归并的节点个数，由于当链表长度非2的整数倍时表长会小于i,故而需要加上p && q的边界判断
                 int x = 0, y = 0;
                 while(x < i && y < i && p && q){
                     if(p->val <= q->val) cur = cur->next = p,p = p->next,x ++; //等号的赋值顺序为从右到左，故而该句意思为
                     //cur->next = p,cur = cur->next,即将小的一点插入cur链表中
                     else cur = cur->next = q,q = q->next,y++;
                 }


                //归并排序基本套路
                 while(x < i && p) cur = cur->next = p,p = p->next,x ++;
                 while(y < i && q) cur = cur->next = q,q = q->next,y ++;
                 cur->next = q; //记得把排好序的链表尾链接到下一链表的表头，循环完毕后q为下一链表表头
            }
        } 
        return dummy->next;
    }
};

作者：yxc
链接：https://www.acwing.com/solution/content/408/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

141. 环形链表

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。

进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：
链表专题 - 图24
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
链表专题 - 图25
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
链表专题 - 图26
输入：head = [1], pos = -1
输出：false
解释：链表中没有环

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


public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null)
        return false;
        ListNode fast=head.next,slow=head;
        while(fast!=slow){
            if (fast == null || fast.next == null) {
                return false;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
        }
    }