[牛客top101]详解01,02,反转链表问题

---

前言

从本章开始,我们就开始刷题旅程啦,路上必定问题多多,但还是得练呐!所以,就现在,开始啦!

---

1. 整体翻转链表

1.1 题目描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0\leq n\leq10000≤n≤1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：

1.2 题目详解

首先呢,我们的思路肯定是要遍历一遍链表,第一个节点指向空,之后把每个链表的next指向前一个节点,那么链表就翻转完成了.所以,我们会用到一个循环.循环的终止条件我们一会再考虑.
怎么具体实现这个过程呢?
假如我们这样将第一个节点的next设置为null

ListNode cur = head;
cur.next = null
1
2

会发现,我们丢失了原本head的next,循环也没法继续.所以呢,在改变每个节点的next值之前,我们需要先把节点原来的next值保存下来
例如这样改变第一个节点

ListNode cur = head;
ListNode curNext = cur.next;
cur.next = null
cur = curNext;
1
2
3
4

那么,怎么将第二个节点的next改成第一个节点呢.
首先,我们肯定是需要将改变第一个节点时就要把它保存下来,
ListNode preCur = cur;但是每次循环,上一次循环中的内容不会被保留,所以,这里,我们要在循环外定义preCur.之后改变第二个节点,cur.next = preCur,就完成第二个节点了.
因为直到最后一个节点,最后一个节点也会进行同样操作,所以,循环结束的条件是(cur != null),不能是(cur.next != null)
综上所述,我们得到循环

public ListNode ReverseList(ListNode head) {
        //找到后一个节点,它的next是preNode,直到node == null
       ListNode  preCur = null;
       ListNode cur = head;
       while(cur != null){
           //因为会改变cur.next,所以,事先要把cur.next存好
           ListNode curNext = cur.next;
           cur.next = preCur;
           //记录下前面的节点,因为循环会刷新数据,所以把pre定义到外面
           preCur = cur;
           cur = curNext;
       }
1
2
3
4
5
6
7
8
9
10
11
12

最后,返回值是啥捏,我们要返回新链表的头结点,也就是返回preCur.

2. 翻转链表的部分区间

2.1 题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.

数据范围： 链表长度 0 < size \le 10000 要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n)
进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)

如下图,翻转链表的2~4(图省事,没画上链子)

2.2 题目详解

这里呢,我们会想到遍历链表,先把指定区间里的节点存起来,都存进去之后,再倒着拿出来,连到区间前的节点后面.说到正着存进去,倒着拿出来,我们很容易就想到了栈,对喽,就是用栈存区间里的节点.
注意这里,得定义一个pre记着从哪之后开始存的,要不,从栈里拿出来的节点不知道连谁的后面.

    	int i = 1;
        ListNode pre = null;
        while(i < m){
            pre = cur;
            cur = cur.next;
            i++;
        }
        //把stack里的节点连到pre后面
        Stack<ListNode> stack = new Stack<>();
        while(i <= n){
            stack.push(cur);
            cur = cur.next;
            i++;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

之后,就可以从栈里拿出节点,连在pre节点后面啦.这里我们要注意一个点,如果区间是从1开始的,就意味着pre为null,在连到pre后面之前,要改一下pre的值.另外,链表的头头也被动了,要想想怎么找链表的头结点.如下图

头结点变成了stack.pop();
代码如下

		if(pre == null){
            pre = stack.pop();
            head = pre;
             while(!stack.isEmpty()){
                ListNode top = stack.pop();
                pre.next = top;
                pre = top;
            }
            pre.next = cur;
            return head;  
        }
1
2
3
4
5
6
7
8
9
10
11

那pre不为null时,就正常往pre后面放就可,如下

		if(pre == null){
            pre = stack.pop();
            head = pre;
             while(!stack.isEmpty()){
                ListNode top = stack.pop();
                pre.next = top;
                pre = top;
            }
            pre.next = cur;
            return head;  
        }else{
            while(!stack.isEmpty()){
                ListNode top = stack.pop();
                pre.next = top;
                pre = pre.next;
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

最后呢,要改一下最后一个被弹出的节点的next值,看看之前,在进站的时候,cur正好走到指定区间的后面,这里直接接上cur就可以.

pre.next = cur;
1

3. 完整代码展示

完整代码如下

public ListNode ReverseList(ListNode head) {
        //找到后一个节点,它的next是preNode,直到node == null
        if(head == null){
            return head;
        }
        ListNode preCur = null;
        ListNode cur = head;
       while(cur != null){
           //因为会改变cur.next,所以,事先要把cur.next存好
           ListNode curNext = cur.next;
           cur.next = preCur;
           //记录下前面的节点,因为循环会刷新数据,所以把pre定义到外面
           preCur = cur;
           cur = curNext;
       }
       return preCur;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

	public ListNode reverseBetween (ListNode head, int m, int n) {
        //区间反转,
        ListNode cur = head;
        if(head == null){
            return null;
        }
        int i = 1;
        ListNode pre = null;
        while(i < m){
            pre = cur;
            cur = cur.next;
            i++;
        }
        //把stack里的节点连到pre后面
        Stack<ListNode> stack = new Stack<>();
        while(i <= n){
            stack.push(cur);
            cur = cur.next;
            i++;
        }
        if(pre == null){
            pre = stack.pop();
            head = pre;
             while(!stack.isEmpty()){
                ListNode top = stack.pop();
                pre.next = top;
                pre = top;
            }
            pre.next = cur;
            return head;  
        }else{
            while(!stack.isEmpty()){
                ListNode top = stack.pop();
                pre.next = top;
                pre = pre.next;
            }
        }
        //加进来了,之后开始弹出元素,连到pre后面
    
        pre.next = cur;
        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
39
40
41
42
43

---