【牛客网-面试必刷TOP 101】01链表

BM1 反转链表

解题思路

第一种方法：借助栈
1. 栈的特点是先进后出，用stack来存储链表，之后新建一个头节点，按出栈顺序拼接形成新的链表。
2. 注意，最后一个节点的next要赋值null
3. 空间复杂度O(N), 时间复杂度O(N)
1
2
3
4

JAVA代码实现

import java.util.*;
public class Solution {
    public ListNode ReverseList (ListNode head) {
        // 用栈，空间复杂度O(N),时间复杂度O(N)
        Stack stack = new Stack<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        //出栈，重新连接
        if(stack.isEmpty()){
            return null;
        }
        ListNode node = stack.pop();
        ListNode dummy = node;
        while(!stack.isEmpty()){
            ListNode tempNode = stack.pop();
            node.next = tempNode;
            node = node.next;
        }
        //最后一个下一位为空
        node.next = null;
        return dummy;
    }
}
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

第二种方法，修改链表指针指向；
指针cur表示当前要处理的节点
指针tmp用于暂存cur.next,避免后面修改指针后，断链无法继续遍历
指针pre表示当前处理节点的上一个节点，进行翻转的目的是将cur.next修改成pre
初始化时，我们将pre设为null，因为第一个节点最后变成最后一个节点，其next为null
1
2
3
4
5

import java.util.*;
public class Solution {
    public ListNode ReverseList (ListNode head) {
        //双指针迭代，空间复杂度O(1),时间复杂度O（N）
        //前继节点为pre，当前操作节点为cur
        //初始化cur为head，pre=null
        ListNode cur = head, pre = null;
        while(cur != null){
            ListNode nextNode = cur.next;//存储下一个节点,不然局部反转的时候会断链
            cur.next = pre;
            pre = cur;
            cur = nextNode;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

BM2 链表内指定区间反转

解题思路

在上一题的基础上进行修改
首先，要处理的cur节点先走m步走到第m个节点
反转结束的条件不是链表遍历到末尾null时候，而是遍历到第n个节点就结束
没有结束额外空间，空间复杂度O(1), 时间复杂度O(N)
1
2
3
4

import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //可以用BM1 反转链表的思想，
        ListNode  dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        //找m
        for (int i = 1; i < m; ++i) {
            pre = cur;
            cur = cur.next;
        }
        //反转m到n
        for (int i = m; i < n; ++i) {
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummy.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

BM3 链表中的节点每k个一组翻转

解题思路

参考了官方解题，递归翻转
设置一个遍历的尾指针tail，每次反转之前找到翻转区间的最后一个节点
如果tail在k步内变成了null，则直接返回，不进行翻转（最后一段不足k个，不翻转）
之后与BM1一样，定义pre，cur，翻转结束的条件是当走到tail，停止翻转
递归的返回值是当前翻转这一分组的头结点
这道题还不是很理解，后面有新的理解再重新整理笔记
1
2
3
4
5
6

import java.util.*;
public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        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

BM4 合并两个排序的链表

解题思路

比较简单，新建一个链表，同时遍历两个链表，比较val的大小，遇到较小的就加入；
1

import java.util.*;
public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        ListNode res = new ListNode(-1);
        ListNode dummy = res;
        while(pHead1 != null && pHead2 != null){
            if(pHead1.val <= pHead2.val){
                dummy.next = pHead1;
                pHead1 = pHead1.next;
            }else{
                dummy.next = pHead2;
                pHead2 = pHead2.next;
            }
            dummy = dummy.next;
        }
        if(pHead1 != null){
            dummy.next = pHead1;
        }
        if(pHead2 != null){
            dummy.next = pHead2;
        }
        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

BM6 判断链表中是否有环

解题思路

是的，没有BM5,因为它是难题，菜的一批的我看答案也还没理解透
利用双指针，slow每次往前走一步，fast每次往前走两步，如果链表中有环，则两个指针最终会在非终点的地方相遇
因为地球是圆的，slow和fast不是平行走，总会在一个时间点遇到的，时长的问题而已     
双指针在后面很多题目中都会遇到过。
1
2
3
4

import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        //快慢指针
        ListNode fast = head;
        ListNode slow = head;
        if(head == null){
            return false;
        }
        // fast.next = head;
        // slow.next = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

BM7 链表中环的入口结点

解题思路

还有借助双指针slow和fast，之后要寻找规律
假设双指针在结点C相遇，且slow是第一次走到C，A->B的距离为X，B->C的距离为Y
则slow走了X+Y，fast每次走的是slow的两倍，所以fast走了2*（X+Y）
fast走的2*（X+Y）实际路径是A->B B->C C->B B->C，我们不知道的是C->B的距离，根据上述条件，可以知道
C->B的距离= 2*（X+Y）-（A->B）-(B->C) -(B->C)= 2*（X+Y）-X-Y-Y=X
噢，原理规律就是，相遇点C->B（环入口）的距离，竟然等于从头结点到环入口的距离
那好办了，slow还是在C开始走，fast回到头结点，和slow一起一步一步走，走到他俩遇见的结点，就是环的入口结点。破案。
1
2
3
4
5
6
7

import java.util.*;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //双指针 空间O(1) 时间O(N)
        if(pHead == null || pHead.next == null){
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //有环，双指针会在环中相遇
            if(slow == fast){
                break;
            }
        }
        if(fast == null || slow == null){
            return null;
        }
        fast = pHead;
        //与第一次相遇的节点相同速度出发，相遇节点为入口结点
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;

    }
}
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

还有一种办法是，不断的遍历链表，借助集合，存储遍历到的结点；
每遍历一个结点判断当前集合中是否已经有这个结点，有的话直接return。
1
2

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //hash 空间O(N) 时间O(N)
        HashSet set = new HashSet<>();
        while(pHead != null){
            if(set.contains(pHead)){
                return pHead;
            }
            set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12

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

解题思路

两次循环，先统计长度，之后遍历到count-k处，return
1

 public ListNode FindKthToTail (ListNode pHead, int k) {
        // 最简单的想法，但是需要两次遍历
        //先遍历，看链表长度，然后遍历count-k次，return
        ListNode dummy = pHead;
        if(pHead == null){
            return pHead;
        }
        int count = 1;
        while(dummy.next != null){
            count++;
            dummy = dummy.next;
        }
        if(count < k){
            return null;
        }
        dummy = pHead;
        while(count > k){
            dummy = dummy.next;
            count --;
        }

        return dummy;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

双指针
fast先走k步
之后fast和slow一起走，当fast走到链表尾部时，slow所在的结点刚好是倒数第k个
1
2
3

public class Solution {
     public ListNode FindKthToTail (ListNode pHead, int k) {
        //快慢指针
        if(pHead == null){
            return pHead;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(k-- > 0){
            if(fast != null){
                fast = fast.next;
            }else{
                return null;
            }
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

BM9 删除链表的倒数第n个节点

解题思路

双指针
注意，有可能删除第1个结点，所以定义一个虚拟头结点res
fast从res开始，先走n步
实际上就是从head开始走了n-1步
当fast走到链表尾部时，slow就走到了倒数第n-1个结点,跳过第n个结点即可：slow.next = slow.next.next
1
2
3
4
5

import java.util.*;
public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // 双指针
        //注意有可能删除第一个，所以使用一个头节点
        if(head == null){
            return head;
        }
        ListNode res = new ListNode(-1);
        res.next = head;

        ListNode slow = res;
        ListNode fast = res;

        //fast先走n步
        for(int i=0;i

第一种方法是先遍历两个链表的长度len1和len2；
如果len1>len2, 链表1先走len1-len2步，因为公共部分在尾部，要尾部对齐；
之后同时遍历链表1和链表2，如果遇到两者相等，直接return（有公共结点会返回，没有会一起走到尾部，返回null）
代码较为繁琐，也可能是我太菜了，不会优化
1
2
3
4

 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            //1.先统计两个链表的长度len1,len2
            ListNode dummy1 = pHead1;
            ListNode dummy2 = pHead2;
            int len1 = 0;
            while(dummy1 != null){
                dummy1 = dummy1.next;
                len1++;
            }
            int len2 = 0;
            while(dummy2 != null){
                dummy2 = dummy2.next;
                len2++;
            }
            //2,较长的链表，指针先走|len1-len2|,因为链表的公共部分在尾部，尾部对齐
            dummy1 = pHead1;
            dummy2 = pHead2;
            if(len1 > len2){
                while(len1 - len2 > 0){
                    dummy1 = dummy1.next;
                    len1--;
                }
            }
            if(len1 < len2){
                while(len2 - len1 > 0){
                    dummy2 = dummy2.next;
                    len2--;
                }
            }
            //3.两个链表同时移动，如果遇到节点相同，return，如果有一方已经=null，直接return null
            while(dummy1 != null && dummy2 != null){
                if(dummy1 == dummy2){
                   return dummy1;
                }else{
                    dummy1 = dummy1.next;
                    dummy2 = dummy2.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

第二种方法，还是双指针，找规律
链表1的长度为len1，链表2的长度为len2，
指针n1和指针n2，一个从链表1出发，一个从链表2出发，两者都走len1+len2个长度
如果有公共结点，如样例{1,2,3}{4,5}{6,7}
/n1走：1，2，3，6，7，null，4，5，6
n2走：4，5，6，7，null，1，2，3，6
走到相等的时候就是公共起始点
没有公共节点如{1}{2,3},{},n1:1,2,3，null  n2:2,3,1，null 走到最后相等都为空
1
2
3
4
5
6
7
8

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode n1 = pHead1;
        ListNode n2 = pHead2;
        while(n1 != n2){
            n1 = (n1 == null)? pHead2 : n1.next;//n1第一次走到空的时候是phead1遍历完
            n2 = (n2 == null)? pHead1 : n2.next;
         }
        return n1;
    }
}
1
2
3
4
5
6
7
8
9
10
11

先把两个链表进行翻转，这样就可以按位加
每个链表结点存储的值在0-9，所以如果计算出来超过9，需要借助变量isTen记录超过9的十位数是多少
链表结点的值取当前位置两个值相加+isTen之后的个位数
1
2
3

import java.util.*;
public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        head1 = reverse(head1);
        head2 = reverse(head2); 
        ListNode ans = new ListNode(-1);
        ListNode dummy = ans;
        int isTen = 0;
        int val=0;
        while(!(head1 == null && head2 == null)){
            val = isTen;
            if(head1 != null){
                val += head1.val;
                head1 = head1.next;
            }
            if(head2 != null){
                val += head2.val;
                head2 = head2.next;
            }
            isTen = val/10;
            dummy.next = new ListNode(val%10);
            dummy = dummy.next;
        }
        if(isTen > 0){
            dummy.next = new ListNode(isTen);
        }
        return reverse(ans.next);
    }

    public ListNode reverse(ListNode head){
        if(head == null){
            return head;
        }
        ListNode cur = head;
        ListNode per = null;
        while(cur!= null){
            ListNode tmp = cur.next;
            cur.next = per;
            per = cur;
            cur = tmp;
        }
        return per;
    }
}
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

借助数组，存储当前链表的所有结点值
对数组进行排序
重新建立链表返回
1
2
3

public class Solution {
    public ListNode sortInList (ListNode head) {
        // 借助数组
        ListNode dummy = head;
        List list = new ArrayList<>();
        while(dummy != null){
            list.add(dummy.val);
            dummy = dummy.next;
        }
        Collections.sort(list);
        dummy = head;
        for(int i=0;i