NC78 反转链表

描述

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

数据范围： n\leq1000n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

img

示例1

输入：

1
{1,2,3}

返回值：

1
{3,2,1}

复制

示例2

输入：

1
{}

返回值：

1
{}

说明：

1
空链表则输出空

思路：

  • 利用next往head列表下一步走
  • 利用pre来保存拼接信息

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head==null) return null;
        ListNode pre = null;
        ListNode next = null;
        while(head!=null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

image-20211226122019794

NC4 判断链表中是否有环

描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围：链表长度 0 \le n \le 100000≤n≤10000，链表中任意节点的值满足 |val| <= 100000∣val∣<=100000

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

输入分为2部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：

img

可以看出环的入口结点为从头结点开始的第1个结点，所以输出true。

示例1

输入：

1
{3,2,0,-4},1

返回值：

1
true

说明：

1
第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->3存在一个链接，组成传入的head为一个带环的链表，返回true

示例2

输入：

1
{1},-1

返回值：

1
false

说明：

1
第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false

示例3

输入：

1
{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

返回值：

1
true

思路：

  • 构建快慢指针
  • 快的走两步，慢的走一步
  • 判断每次只能判断当前与下一步的所指情况，否则容易出现越界的问题（null.next）

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }
}

NC3 链表中环的入口结点

描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围：n*≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

img

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1

输入：

1
{1,2},{3,4,5}

返回值：

1
3

说明：

1
返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

示例2

输入：

1
{1},{}

返回值：

1
"null"

说明：

1
没有环，返回对应编程语言的空结点，后台程序会打印"null"

示例3

输入：

1
{},{2}

返回值：

1
2

说明：

1
环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

思路：

  • 设置快慢指针，假如有环，他们最后一定相遇。
  • 两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。

解答：

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
/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode low = pHead;
        ListNode fast = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
            if(fast == low) break;
        }
        
        if(fast == null || fast.next == null) return null;
        
        low = pHead;
        while (fast!=low) {
            fast = fast.next;
            low = low.next;
        }
        return low;
    }
}

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

描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围： \ 0 \le n \le 2000 0≤n≤2000 ， 1 \le k \le 20001≤k≤2000 ，链表中每个元素都满足 0 \le val \le 10000≤val≤1000
要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如：

给定的链表是 1\to2\to3\to4\to51→2→3→4→5

对于 k = 2k=2 , 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5

对于 k = 3k=3 , 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5

示例1

输入：

1
{1,2,3,4,5},2

返回值：

1
{2,1,4,3,5}

示例2

输入：

1
{},1

返回值：

1
{}

思路：

  • 写一个计算链表长度的子函数，并对链表进行分块
  • 设置一个result存返回值，一个now=result对now进行操作，实际改变了result的值
  • 每一块进行反转
    • 一个for循环，每次head向前移一位
    • head.next存tmp
    • tmp存当前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
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if (k <= 1) return head;
        if (head == null) return head;
        ListNode node = head;
        int len = length(head);
        int block = len/k;
        
        ListNode result = new ListNode(0);    //用来返回值，保存结果
        ListNode now = result;    //用来移动，操作
        for(int i = 0; i < block; i++) {
            ListNode tmp = null;
            for (int j = 0; j < k; j ++) {    //将第i块的元素翻转
                ListNode bl = head.next;
                head.next = tmp;
                tmp = head;
                head = bl;
            }
            now.next = tmp; 
            while(now.next != null) now = now.next;    //将now更新到最前的一个点
        }
        now.next = head;    //这里的head已经移到了最后一块不可分割的地方
        return result;
    }
    
    public int length(ListNode now) {
        int length = 0;
        while (now!=null) {
            length++;
            now = now.next;
        }
        return length;
    }
}

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

描述

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围： 链表节点数 0 \le n \le 10^70≤n≤107，链表中每个节点的值满足 |val| \le 10^7∣val∣≤107

示例1

输入：

1
{1}

返回值：

1
true

示例2

输入：

1
{2,1}

返回值：

1
false

说明：

1
2->1

示例3

输入：

1
{1,2,2,1}

返回值：

1
true

说明：

1
1->2->2->1

思路：

  • a链表=b链表 a变b也变
  • 快慢指针找到中点
  • 只反转后半段

解答：

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
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) {
        // write code here
        if (head.next == null || head == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next;
        fast = reverse(fast);
        while(fast !=null) {
            if(head.val != fast.val) return false;
            head = head.next;
            fast = fast.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode next= null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

NC40 两个链表生成相加链表

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0 \le n,m \le 10000000≤n,m≤1000000，链表任意值 0 \le val \le 90≤val≤9
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

img

示例1

输入：

1
[9,3,7],[6,3]

返回值：

1
{1,0,0,0}

说明：

1
如题面解释

示例2

输入：

1
[0],[6,3]

返回值：

1
{6,3}

备注：

1
2
1 \leq n, m \leq 10^61≤n,m≤106
0 \leq a_i, b_i \leq 90≤ai,bi≤9

思路：

  • 反转相加，注意进位
  • 构造新的链表 （一定得有初始值） ListNode head = new ListNode(-1);
  • 添加链表的节点需要new一个新的链表 cur.next = new ListNode(val % 10)

解答：

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
import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        int carry = 0;
        while((head1 != null) || (head2 != null)) {
            int val = carry;
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            cur.next = new ListNode(val % 10);
            carry = val / 10;
            cur = cur.next;
        }
        if (carry == 1) cur.next = new ListNode(carry);
        return reverse(head.next);
    }
    
    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

剑指 Offer II 077. 链表排序

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

示例 1：

img

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

示例 2：

img

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

示例 3：

1
2
输入：head = []
输出：[]

解答：

  • 先存入数组，然后sort排序，然后存回链表
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
/**
 * 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 {

    //先存入数组，然后sort排序，然后存回链表
    public ListNode sortList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode cur = head;
        while(cur != null) {
            list.add(cur.val);
            cur = cur.next;
        }
        Collections.sort(list);
        ListNode p = head;

        for(int i = 0; i < list.size(); i++) {
            p.val = list.get(i);
            p = p.next;
        }
        return head;
    }
}