算法：链表（力扣+牛客经典题）_牛客网和力扣网算法

链表

力扣

203. 移除链表元素

思路：使用while循环每找到指定的值，就把下一个节点指向下下个节点的位置

/**
 * 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 removeElements(ListNode head, int val) {
        // 初始化链表 第一个值为0
        ListNode listNode = new ListNode(0,head);
        // 因为单链表是不可逆的，所以把listNode的 地址赋给 temp，就可以控制temp来操作链表，
        ListNode temp = listNode;
        // 循环找值，并去掉
        while (temp.next != null){
            if (temp.next.val == val){
                // 如果temp.next有值，最不济temp.next.next为null，而把null重新赋给temp.next也不会报空节点异常
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        // 因为listNode的初始值为0，他的下一个才是原数组head（删掉了指定的值）
        return listNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

206. 反转链表

思路：就是先设一个值为null，再用head开头的值指向这个null，再把head指向下一个，重复

/**
 * 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 reverseList(ListNode head) {
        ListNode a = null;
        ListNode listNode = head;
        // 循环这个链表
        while (listNode!=null){
            // 设置一个b指向listNode 的下一个节点
            ListNode b = listNode.next;
            // listNode最前面的值的后一个指向a这个链表
            listNode.next = a;
            // 再把listNode这个链表赋给a
            a = listNode;
            // listNode 指向他的下一个节点，用于循环
            listNode = b;
        }
        return a;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

思路：每次找到要旋转的个数，并旋转，剩余的链表进入递归，并挨个拼接

/**
 * 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 listNode = reverseKGroup(head, 2);
        return listNode;
    }
    public ListNode reverseKGroup (ListNode head, int k) {
        //找到每次翻转的尾部
        ListNode tail = head;
        //遍历k次到尾部
        for(int i = 0; i < k; i++){
            //如果不足k到了链表尾，直接返回，不翻转
            if(tail == null) {
                return head;
            }
            tail = tail.next;
        }
        // 这里就是翻转链表的知识点
        //翻转时需要的前序和当前节点
        ListNode pre = null;
        ListNode cur = head;
        //在到达当前段尾节点前
        while(cur != tail){
            //翻转
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //当前尾指向下一段要翻转的链表
        head.next = reverseKGroup(tail, k);
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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

思路：使用双指针，先让前节点走N+1步，后节点不动，然后遍历前节点，直到前节点指向null的时候，后节点的节点指向倒数N个节点的前一个节点

/**
 * 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 x = new ListNode(0,head);
        ListNode a = x;
        // 这一步和下面的for循环就是指，b链表要先走n+1步
        ListNode b = x.next;
        for (int i = 0; i < n; i++) {
            b = b.next;
        }
        // 通过b走到头了之后，a链表指向的就是倒数n+1个节点
        while (b!=null){
            a = a.next;
            b = b.next;
        }
        // a下一个节点直线a的下下个节点就可以了
        a.next = a.next.next;
        return x.next ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

160.链表相交

思路：意思就是说两个链表后面节点可能相同，那么后面的长度也是一样的，就需要把前面长的链表给截成和短的链表一样长，然后进行比较，不一样就一起后移

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 使用AL和BL记录两个链表的长度
        int AL = 0;
        int BL = 0;
        ListNode aL = headA;
        ListNode bL =headB;
        while (aL!=null){
            AL++;
            aL = aL.next;
        }
        while (bL!=null){
            BL++;
            bL = bL.next;
        }
        aL = headA;
        bL = headB;
        // 截取长的链表，使两个链表一样长
        if (AL > BL){
            for (int i = 0; i < AL - BL; i++) {
                aL = aL.next;
            }
        }else {
            for (int i = 0; i < BL - AL; i++) {
                bL = bL.next;
            }
        }
        // 循环比较是否相同，返回相同的部分
        while (aL!=null){
            if (aL == bL){
                return aL;
            }
            aL = aL.next;
            bL = bL.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

142.环形链表 II

思路：一、先要判断是否是循环链表；二、要找出循环入口节点

一判断是否循环

使用快慢指针，前指针每次走两个节点，后指针每次走一个节点，如果是循环链表的话，前一个指针会追上后一个指针的，可以做一下试验：

如示例一：前走两步，后走一步

两个从三开始

第一次：前：2,0；后：2；

第二次：前：-4,2；后：0；

第三次：前：0,-4；后：-4；

结束

二、要找出循环入口节点

先定位到判断循环链表的那个节点，如上诉的0这个节点，再从开头（3）走一个值，他们两个每次只走一步，如果他们相等的话，就是那个节点循环的头

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode left = head;
        ListNode right = head;
        // 因为right要走两步，怕出现空指针异常（如果 right.next 为null的话，right.next.next就会空指针异常）
        while (right != null && right.next != null){
            // 判断是否循环
            left = left.next;
            right = right.next.next;
            if (left == right){
                left = head;
                // 找循环的头节点
                while (left != right){
                    left = left.next;
                    right = right.next;
                }
                return left;
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

牛客：

BM1 反转链表（同力扣：206.循环链表，上面有讲）

BM2 链表内指定区间反转

思路：截取翻转，并连接

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //设置虚拟头节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        //1.走left-1步到left的前一个节点
        for(int i=0;i<m-1;i++){
            pre = pre.next;
        }

        //2.走roght-left+1步到right节点
        ListNode rigthNode = dummyNode;
        for(int i=0;i<n;i++){
            rigthNode = rigthNode.next;
        }

        //3.截取出一个子链表
        ListNode leftNode = pre.next;
        ListNode cur = rigthNode.next;

        //4.切断链接
        pre.next=null;
        rigthNode.next=null;

        //5.反转局部链表
        reverseLinkedList(leftNode);

        //6.接回原来的链表
        pre.next = rigthNode;
        leftNode.next = cur;
        return dummyNode.next;
    }
    //反转局部链表
    private void reverseLinkedList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            //Cur_next 指向cur节点的下一个节点
            ListNode Cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = Cur_next ;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

BM3 链表中的节点每k个一组翻转（同力扣：24. 两两交换链表中的节点，上面有讲）

BM4 合并两个排序的链表

思路：一直循环，比较两个链表当时的大小，小的那个加入新的链表，并指向后一个节点，大的链表不动，最后哪个链表还有剩的话，就自动加入后面就可以了

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode listNode = new ListNode(-1);
        // 新的链表
        ListNode x = listNode;
        while (list1 != null&&list2!=null){
            // 判断哪个链表的节点大，把小的节点接入新的链表
            if (list1.val > list2.val){
                x.next = list2;
                x = x.next;
                list2 = list2.next;
            }else {
                x.next = list1;
                x = x.next;
                list1 = list1.next;
            }
        }
        //哪个链表还有剩，直接连在后面
        if(list1 != null)
            x.next = list1;
        else
            x.next = list2;
        return listNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

BM5 合并k个已排序的链表

思路：这里使用了PriorityQueue优先队列（最小堆），这个数据结构可以把最小值顶到堆的最前面，使用我只需要，把list里面的所有值放入最小堆里面，然后遍历最小堆，得到一个完整的新链表就可以了

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // 优先队列（最小堆）
        Queue<Integer> queue = new PriorityQueue<>();
        // 加入最小堆里面
        lists.forEach(x->{
            while (x!=null){
                queue.offer(x.val);
                x = x.next;
            }
        });
        // 新建一个链表用来装遍历最小堆的最前面就可以了
        ListNode listNode = new ListNode(-1);
        ListNode x = listNode;
        while (!queue.isEmpty()){
            x.next = new ListNode(queue.poll());
            x = x.next;
        }
        return listNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

BM6 判断链表中是否有环（同力扣：142.环形链表 II的第一个观点寻找循环链表，上面有讲）

BM7 链表中环的入口结点（同力扣：142.环形链表 II的第二个观点寻找循环链表入口节点，上面有讲）

BM8 链表中倒数最后k个结点

思路：双指针，先让前节点走N+1步，后节点不动，然后遍历前节点，直到前节点指向null的时候，后节点的节点指向倒数N个节点的前一个节点

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead==null){
            return pHead;
        }
        ListNode x = pHead;
        for (int i = 0; i < k; i++) {
            if (x == null){
                return null;
            }
            x = x.next;
        }
        ListNode y = pHead;
        while (x != null){
            x = x.next;
            y = y.next;
        }
        return y;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

BM9 删除链表的倒数第n个节点（同力扣：19. 删除链表的倒数第 N 个结点，上面有讲）

BM10 两个链表的第一个公共结点（同力扣：160.链表相交，上面有讲）

BM11 链表相加(二)

思路：先翻转两个链表（因为加法都是从个位加着走，所以翻转一个从头一个加到尾，再翻转一下，就是我们需要的值），就是取到每个节点值相加，如果进位就往前加一个，如果到最后一个节点还需要进位，就再下一个节点输入一。

import java.util.*;

import java.math.BigInteger;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 翻转
        ListNode a = reverse(head1);
        ListNode b = reverse(head2);
        // c是判断需要进位不，如果是0就是没进位，1就是需要进位的那个加上1
        int c = 0;
        // x是a链表节点的值
        int x = 0;
        // y是b链表节点的值
        int y = 0;
        // 通过d来记录listNode的地址，listNode变动的时候，d还是指向没变动的头结点
        ListNode listNode = new ListNode(-1);
        ListNode d = listNode;
        while (a!=null||b!=null){
            // 给x赋值
            if (a!=null){
                x = a.val;
                a = a.next;
            }else {
                x = 0;
            }
            // 给y赋值
            if (b!=null){
                y = b.val;
                b = b.next;
            }else {
                y = 0;
            }
            // 让listNode.next指向新建一个链表
            // (x+y+c)%10 可以得到个位的值，存入新的链表
            listNode.next = new ListNode((x+y+c)%10);
            listNode = listNode.next;
            // 判断是否进位 如果十位有值 c就位十位的值
            c = (x + y + c)/10;
        }
        // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
        if(c > 0){
            listNode.next = new ListNode(c);
        }
        // 再次翻转
        return reverse(d.next);
    }

    // 反转链表
    ListNode reverse(ListNode head){
        if(head == null) {
            return head;
        }
        ListNode cur = head;
        ListNode node = null;
        while(cur != null){
            ListNode tail = cur.next;
            cur.next = node;
            node = cur;
            cur = tail;
        }
        return node;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

BM12 单链表的排序

思路：一、变成数组然后排序重新写入链表；二、使用PriorityQueue优先队列（最小堆）排序取值就可以了

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // 最小堆
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        // 存入最小堆
        while (head!=null){
            queue.add(head.val);
            head = head.next;
        }
        ListNode listNode = new ListNode(-1);
        ListNode x = listNode;
        // 从最小堆取值，然后组成新的数组
        while (!queue.isEmpty()){
            listNode.next = new ListNode(queue.poll());
            listNode = listNode.next;
        }
        return x.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

BM13 判断一个链表是否为回文结构

思路：把链表的值写入一个数组里面，然后利用双指针判断是否是回文就可以了（就是第一个指针指向头，后一个指针指向尾，判断是否相等，相等就向前比较就可以了）

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        // 变成一个list集合
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        int x = 0;
        int y = list.size() - 1;
        // 双指针判断是否为回文
        while (x<y){
            if (!list.get(x++).equals(list.get(y--))){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

BM14 链表的奇偶重排

思路：看代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        //如果链表为空，不用重排
        if(head == null) 
            return head;
        //even开头指向第二个节点，可能为空
        ListNode even = head.next; 
        //odd开头指向第一个节点
        ListNode odd = head; 
        //指向even开头
        ListNode evenhead = even; 
        while(even != null && even.next != null){
            //odd连接even的后一个，即奇数位
            odd.next = even.next; 
            //odd进入后一个奇数位
            odd = odd.next; 
            //even连接后一个奇数的后一位，即偶数位
            even.next = odd.next; 
            //even进入后一个偶数位
            even = even.next; 
        } 
        //even整体接在odd后面
        odd.next = evenhead; 
        return head;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

BM15 删除有序链表中重复的元素-I

思路：因为是有序的，所以只要后一个节点的值与自己节点一样，把后一个节点指向下下个节点就可以了

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        ListNode a = head;
        while (head!=null && head.next!=null){
            // 如果后一个节点和自己节点值相等的话，就删除掉，并不需要移动自己的指针
            if (head.val == head.next.val){
                head.next = head.next.next;
                continue;
            }
            head = head.next;
        }
        return a;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

BM16 删除有序链表中重复的元素-II

思路：添加一个表头，然后看下一个节点与下下个节点是否相同，如果相同，再循环看看后面的节点的值是否一样，相同就全部跳过

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        //空链表
        if(head == null)
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp)
                    cur.next = cur.next.next;
            }
            else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38