数据结构与算法_04_链表

数据结构与算法
发布日期:   2021-10-16
更新日期:   2021-11-11
文章字数:   7.2k
阅读时长:   32 分
阅读次数:  

本文介绍一种新的数据结构——链表。

1. 链表理论基础

1.1 链表

前面提到的数组、队列和栈等数据结构，各个元素实际在内存空间中是连续存储的，也就是说这种数据结构需要在内存空间中开辟一块连续的空间。和剪纸一样，如果总是开辟大块空间，那么就会剩下很多零碎的小空间，内存空间浪费太多，这些小空间该怎么利用起来呢？可以利用零碎的小空间形成的新型数据结构——链表。

链表，顾名思义，是一条链，也是一张表。链——将若干个单元连接起来，表——连接起来的单元形成一个线性结构，可以逐个访问。

链表是一种通过指针将节点串联在一起的线性结构，每一个节点由两部分组成，一个是数据域（存放实际数据），一个是指针域（存放下一节点的指针/引用），最后一个节点的指针指向null（空指针，不存储任何东西）。链表的头部节点称为头节点，尾部称为尾节点。

DSAA_011.png (752×183) (gitee.io)

1.2 链表的操作

针对链表的操作主要有以下几种：

1.2.1 删除节点

将该节点删除，即将其从链上删除。

  • 删除非头尾节点：

    比较直观的做法是将该节点的前一个节点的引用区指向该节点的后一个节点。那么该节点就不会被链访问到。此时可能会有疑问，实际上该节点仍然存储在内存空间上，只不过不在链上。的确是这样，删除节点指的就是将其从链上删除，并不是指的是从内存空间上删除。如果该节点没有其他引用指向它，那么Java、Python等内存回收机制会自动释放该节点的内存空间；如果是C++等语言，则需要手动释放该内存空间。

  • 删除头节点：

    直接将头指针指向当前头节点的下一个节点即可。

  • 删除尾节点：

    直接将尾节点的上一个节点指向null即可。

DSAA_014.png (748×205) (gitee.io)

1.2.2 添加节点

添加节点，也类似。

  • 插入非头尾节点：

    将插入节点的引用区指向插入位置节点，将插入位置上一个节点的引用区指向插入节点。

  • 插入头节点：

    将插入节点的引用区指向头结点，将头指针指向插入节点。

  • 插入尾节点：

    将尾结点的引用区指向插入节点，将插入节点的引用区指向null。

DSAA_015.png (762×289) (gitee.io)

1.3 链表的类型

1.3.1 单链表

链表最基本的类型就是单链表，即上图所示。因为后一个节点的引用存储在前一个节点中，所以只能通过前一个节点来访问后一个节点。

1.3.2 双链表

在单链表的基础上，为了更方便的访问节点，可以在节点中增加一块空间，存储前一个节点的引用。这样，引用形成的链就是双向的，既可以向前查询，也可以向后查询。

DSAA_017.png (756×160) (gitee.io)

1.3.3 循环链表

循环链表，顾名思义，就是链表首尾相连，即尾结点的指针指向头结点，尾结点存储头结点的引用。

DSAA_012.png (475×455) (gitee.io)

1.4 链表的存储方式

前面提到过，数组各个元素在内存中是连续分布的，而链表在内存中则不一定。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点可以不是连续分布的，可以散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

DSAA_013.png (515×367) (gitee.io)

如上所示，该链表的头节点为2，尾节点为7，各个节点分布在内存不同地址空间上，通过引用串联在一起。

1.5 链表与数组对比

从原理上就可以看到，数组可以通过下标索引到任意元素，即查询的时间复杂度为O(1)，而链表只能通过上一个节点索引到当前节点，即只能从头开始遍历，查询的时间复杂度为O(n)。而针对插入删除等操作，需要重新定义数组，并且需要移动元素，时间复杂度为O(n)，而链表则是开辟一个元素空间，将其插入即可，时间复杂度为O(1)。

DSAA_016.png (775×320) (gitee.io)

1.6 链表的Java实现

下面简单实现一下上述的三种链表。为了方便操作，可以设置一个虚拟头节点；当然也可以不设置，直接在原始节点进行操作。

1.6.1 单链表实现

单链表的节点有两个元素，一个存储节点的值，一个保存下一个节点的引用，主要提供设置下一个节点和获取下一个节点的方法。节点的实现代码如下：

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
class SimpleLinkedNode{
    private Object node;
    private SimpleLinkedNode next;

    public SimpleLinkedNode(){}

    public SimpleLinkedNode(Object node){
        this.node = node;
        this.next = null;
    }

    public boolean setNext(Object next){
        if(next instanceof SimpleLinkedNode || null == next){
            this.next = (SimpleLinkedNode) next;
            return true;
        }
        return false;
    }

    public boolean hasNext(){
        return null != this.next;
    }

    public Object getNext(){
        return this.next;
    }

    public Object getValue(){
        return this.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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
class SimpleLinkedList{
    private SimpleLinkedNode head;
    private int length;

    public SimpleLinkedList(){}

    public SimpleLinkedList(SimpleLinkedNode sln){
        this.head = sln;
        this.length = 1;
    }

    public boolean addHead(SimpleLinkedNode sln){
        if(sln.setNext(this.head)){
            this.head = sln;
            this.length++;
            return true;
        }
        return false;
    }

    public boolean addTail(SimpleLinkedNode sln){
        // 注意，要找到尾结点
        SimpleLinkedNode temp = this.head;
        while(temp.hasNext()){
            temp = (SimpleLinkedNode) temp.getNext();
        }

        if(temp.setNext(sln)){
            this.length++;
            return true;
        }

        return false;
    }

    public boolean addNode(int index, SimpleLinkedNode sln){
        // index 从0开始，小于length。
        if(index <= 0 || index >= this.length){
            return false;
        }

        SimpleLinkedNode temp = this.head;

        for (int i = 1; i < index; i++) {
            temp = (SimpleLinkedNode) temp.getNext();
        }

        if(sln.setNext(temp.getNext()) && temp.setNext(sln)){
            this.length++;
            return true;
        }

        return false;
    }

    public void delHead(){
        this.head = (SimpleLinkedNode) this.head.getNext();
        this.length--;
    }

    public void delTail(){
        SimpleLinkedNode temp = this.head;

        if(this.length == 1){
            delHead();
            return;
        }

        while(((SimpleLinkedNode) temp.getNext()).hasNext()){
            temp = (SimpleLinkedNode) temp.getNext();
        }

        // null 似乎可以作为参数传入
        if(temp.setNext(null)){
            this.length--;
        }
    }

    public boolean delNode(int index){
        if(index <= 0 || index >= this.length){
            return false;
        }

        SimpleLinkedNode temp = this.head;

        for (int i = 0; i < index; i++) {
            temp = (SimpleLinkedNode) temp.getNext();
        }

        if(temp.setNext(((SimpleLinkedNode) temp.getNext()).getNext())){
            this.length--;
            return true;
        }

        return false;

    }

    public void getValueByIndex(int index){
        if(index < 0 || index >= this.length){
            return;
        }

        SimpleLinkedNode sln = this.head;

        if(0 == index){
            System.out.println(sln.getValue());
            return;
        }

        for (int i = 1; i < index + 1; i++) {
            sln = (SimpleLinkedNode) sln.getNext();
        }

        System.out.println(sln.getValue());

    }

    public void getValue(){
        SimpleLinkedNode temp = this.head;

        while(temp.hasNext()){
            System.out.print(temp.getValue() + "-->");
            temp = (SimpleLinkedNode) temp.getNext();
        }

        System.out.println(temp.getValue() + ".");
    }
}

测试代码如下所示：

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
public class linkedListTest01 {

    public static void main(String[] args) {

        SimpleLinkedNode sln = new SimpleLinkedNode("Hello");

        SimpleLinkedList sll = new SimpleLinkedList(sln);

        sll.addTail(new SimpleLinkedNode("world"));
        sll.addTail(new SimpleLinkedNode("My"));
        sll.addTail(new SimpleLinkedNode("name"));
        sll.addTail(new SimpleLinkedNode("zhang"));

        sll.getValue();

        sll.addNode(4, new SimpleLinkedNode("is"));

        sll.getValue();

        sll.addHead(new SimpleLinkedNode("Hi"));

        sll.getValue();

        sll.delHead();

        sll.getValue();

        sll.delTail();

        sll.getValue();

        sll.addTail(new SimpleLinkedNode("Li"));

        sll.getValue();

        sll.delNode(4);

        sll.getValue();

        sll.addTail(new SimpleLinkedNode("wang"));

        sll.getValue();
        
        sll.getValueByIndex(3);

    }
}

1.6.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
32
33
34
35
36
37
38
39
40
41
42
class DoubleLinkedNode{

    private Object node;
    private DoubleLinkedNode pre;
    private DoubleLinkedNode next;

    public DoubleLinkedNode(){}

    public DoubleLinkedNode(Object node){
        this.node = node;
        this.pre = null;
        this.next = null;
    }

    public boolean setPre(Object pre){
        if(pre instanceof DoubleLinkedNode){
            this.pre = (DoubleLinkedNode) pre;
            return true;
        }
        return false;
    }

    public boolean setNext(Object next){
        if(next instanceof DoubleLinkedNode || null == next){
            this.next = (DoubleLinkedNode) next;
            return true;
        }
        return false;
    }

    public Object getValue(){
        return this.node;
    }

    public Object getNext(){
        return this.next;
    }

    public Object getPre(){
        return this.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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
class DoubleLinkedList{
    // 采用虚拟头结点的方式
    private DoubleLinkedNode head;
    private int length;

    public DoubleLinkedList(){}

    public DoubleLinkedList(DoubleLinkedNode head){
        this.head = head;
        this.length = 0;
    }

    public boolean addHead(DoubleLinkedNode dln){
        if(0 == this.length){
            if(this.head.setNext(dln) && dln.setPre(this.head)){
                this.length++;
                return true;
            }
            return false;
        }

        if(dln.setNext(this.head.getNext()) && ((DoubleLinkedNode) this.head.getNext()).setPre(dln) && this.head.setNext(dln) && dln.setPre(this.head)){
            this.length++;
            return true;
        }

        return false;
    }

    public boolean addTail(DoubleLinkedNode dln){

        DoubleLinkedNode temp = this.head;
        for (int i = 0; i < this.length; i++) {
            temp = (DoubleLinkedNode) temp.getNext();
        }

        if(temp.setNext(dln) && dln.setPre(temp)){
            this.length++;
            return true;
        }

        return false;
    }

    public boolean addNode(int index, DoubleLinkedNode dln){

        if(index <= 0 || index >this.length){
            return false;
        }

        DoubleLinkedNode temp = this.head;
        for (int i = 0; i < index; i++) {
            temp = (DoubleLinkedNode) temp.getNext();
        }

        if(dln.setNext(temp.getNext()) && ((DoubleLinkedNode) temp.getNext()).setPre(dln) && temp.setNext(dln) && dln.setPre(temp)){
            this.length++;
            return false;
        }
        return false;
    }

    public boolean delHead(){

        DoubleLinkedNode temp = (DoubleLinkedNode) this.head.getNext();

        if(this.head.setNext(temp.getNext()) || ((DoubleLinkedNode) temp.getNext()).setPre(this.head)){
            this.length--;
            return true;
        }

        return false;
    }

    public boolean delTail(){

        DoubleLinkedNode temp = this.head;

        for (int i = 0; i < this.length - 1; i++) {
            temp = (DoubleLinkedNode) temp.getNext();
        }

        // 注意，传参null时的判断
        if(temp.setNext(null)){
            this.length--;
            return true;
        }

        return false;
    }

    public boolean delNode(int index){

        DoubleLinkedNode temp = this.head;

        for (int i = 0; i < index; i++) {
            temp = (DoubleLinkedNode) temp.getNext();
        }

        DoubleLinkedNode dln = (DoubleLinkedNode) temp.getNext();
        if(temp.setNext(dln.getNext()) && ((DoubleLinkedNode) dln.getNext()).setPre(temp)){
            this.length--;
            return true;
        }
        return false;
    }

    public void getValueByIndex(int index){

        DoubleLinkedNode temp = this.head;

        for (int i = 0; i < index + 1; i++) {
            temp = (DoubleLinkedNode) temp.getNext();
        }
        System.out.println(temp.getValue());
    }

    public void getValue(){
        DoubleLinkedNode temp = (DoubleLinkedNode) this.head.getNext();
        for (int i = 0; i < this.length - 1; i++) {
            System.out.print(temp.getValue() + "--->");
            temp = (DoubleLinkedNode) temp.getNext();
        }
        System.out.println(temp.getValue());

        System.out.println("========================以下是根据this.pre指针逆序输出");
        for (int i = 0; i < this.length - 1; i++) {
            System.out.print(temp.getValue() + "<---");
            temp = (DoubleLinkedNode) temp.getPre();
        }
        System.out.println(temp.getValue());
        System.out.println();
    }
}

测试代码如下：

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
public class LinkedListTest02 {

    public static void main(String[] args) {

        DoubleLinkedNode dln = new DoubleLinkedNode(null);

        DoubleLinkedList dll = new DoubleLinkedList(dln);

        dll.addTail(new DoubleLinkedNode("Hello"));
        dll.addTail(new DoubleLinkedNode("world"));
        dll.addTail(new DoubleLinkedNode("My"));
        dll.addTail(new DoubleLinkedNode("name"));
        dll.addTail(new DoubleLinkedNode("zhang"));

        dll.getValue();

        dll.addNode(4, new DoubleLinkedNode("is"));

        dll.getValue();

        dll.addHead(new DoubleLinkedNode("Hi"));

        dll.getValue();

        dll.delHead();

        dll.getValue();

        System.out.println("-----------");
        dll.delTail();

        dll.getValue();

        dll.addTail(new DoubleLinkedNode("Li"));

        dll.getValue();

        dll.delNode(4);

        dll.getValue();

        dll.addTail(new DoubleLinkedNode("wang"));

        dll.getValue();

        dll.getValueByIndex(3);
    }
}

1.6.3 循环链表实现

循环链表和单链表没什么区别，只是尾结点的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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class CycleLinkedList{

    private SimpleLinkedNode head;
    private int length;

    public CycleLinkedList(){}

    public CycleLinkedList(SimpleLinkedNode head){
        this.head = head;
        this.head.setNext(this.head);   // 循环，尾指针指向头节点。
        this.length = 1;
    }

    public boolean addNodeByIndex(int index, SimpleLinkedNode sln){

        if(index < 0 || index > this.length){
            return false;
        }

        SimpleLinkedNode temp = this.head;

        if(0 == index){

            for (int i = 1; i < this.length; i++) {
                temp = (SimpleLinkedNode) temp.getNext();
            }

            if(temp.setNext(sln) && sln.setNext(this.head)){
                this.head = sln;
                this.length++;
                return true;
            }

            return false;
        }



        for (int i = 1; i < index; i++) {
            temp = (SimpleLinkedNode) temp.getNext();
        }

        SimpleLinkedNode slns = (SimpleLinkedNode) temp.getNext();

        if(temp.setNext(sln) && sln.setNext(slns)){
            this.length++;
            return true;
        }

        return false;
    }

    public boolean delNodeByIndex(int index){

        if(index < 0 || index > this.length){
            return false;
        }

        SimpleLinkedNode temp = this.head;

        if(0 == index){
            for (int i = 1; i < this.length; i++) {
                temp = (SimpleLinkedNode) temp.getNext();
            }

            if(temp.setNext(this.head.getNext())){
                this.head = (SimpleLinkedNode) temp.getNext();
                this.length--;
                return true;
            }
            return false;
        }

        for (int i = 1; i < index; i++) {
            temp = (SimpleLinkedNode) temp.getNext();
        }

        if(temp.setNext(((SimpleLinkedNode) temp.getNext()).getNext())){
            this.length--;
            return true;
        }

        return false;
    }

    public void getValue(){

        SimpleLinkedNode temp = this.head;

        for (int i = 1; i < this.length; i++) {
            System.out.print(temp.getValue() + "--->");
            temp = (SimpleLinkedNode) temp.getNext();
        }

        System.out.println(temp.getValue());
    }

    /**
     * 测试是否构成循环链表
     */
    public void cyclePrint(){
        SimpleLinkedNode temp = this.head;

        while(temp.hasNext()){
            System.out.print(temp.getValue() + "--->");
            temp = (SimpleLinkedNode) temp.getNext();
        }

        System.out.println(temp.getValue());
    }
}

测试代码如下所示：

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
public class LinkedListTest03 {

    public static void main(String[] args) {

        SimpleLinkedNode sln = new SimpleLinkedNode("Hello");

        CycleLinkedList cll = new CycleLinkedList(sln);

        cll.addNodeByIndex(1, new SimpleLinkedNode("world"));

        cll.getValue();

        cll.addNodeByIndex(2, new SimpleLinkedNode("My"));
        cll.addNodeByIndex(3, new SimpleLinkedNode("name"));
        cll.addNodeByIndex(4, new SimpleLinkedNode("is"));
        cll.addNodeByIndex(5, new SimpleLinkedNode("zhang"));
        cll.addNodeByIndex(6, new SimpleLinkedNode("san"));

        cll.getValue();

        cll.addNodeByIndex(0, new SimpleLinkedNode("Hi"));

        cll.getValue();

        cll.addNodeByIndex(8,new SimpleLinkedNode("well"));

        cll.getValue();

        cll.delNodeByIndex(0);

        cll.getValue();

        cll.delNodeByIndex(7);

        cll.getValue();

        cll.delNodeByIndex(1);

        cll.getValue();

        cll.addNodeByIndex(1, new SimpleLinkedNode("world"));

        cll.getValue();

        cll.cyclePrint();   // 测试是否构成环

    }
}

2. 链表经典题目

2.1 翻转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->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
public static void reverseLinkedList(SimpleLinkedList sll){

    SimpleLinkedNode mid = sll.getHeaad();

    SimpleLinkedNode slow = mid;

    SimpleLinkedNode fast = (SimpleLinkedNode) mid.getNext();

    slow.setNext(null);	// 注意，修改“头节点”的next为null。

    while(fast != null){

        mid = fast;
        fast = (SimpleLinkedNode) fast.getNext();

        mid.setNext(slow);

        slow = mid;
    }
    
    // 输出
    while(slow.hasNext()){
        System.out.print(slow.getValue() + "-->");
        slow = (SimpleLinkedNode) slow.getNext();
    }

    System.out.println(slow.getValue() + ".");
}

2.2 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例：输入：1->2->3->4；输出：2->1->4->3

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

题目中提到要交换节点的位置，所以新开辟链表是行不通的。两两交换，至少需要知道两元素的上一个节点，这样才能保证链表的连接性。所以对于开始的两个节点，需要单独考虑。

DSAA_018.png (604×325) (gitee.io)

那么如何知道某个节点究竟是和上一个节点交换还是和下一个节点交换呢？可以先考虑一般性，然后再考虑特殊性(开始两个节点)。以上图为例，3和4交换，设置三个变量：slow用于保存两个节点的上一个节点2，fast用于保存两个节点的第一个节点3，temp用于保存两个节点的第二个节点4。设置slow的下标index，如果slow当前下标是2，那么将fast和temp进行交换。部分代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(index % 2 == 0){
    temp = (SimpleLinkedNode) fast.getNext();

    if(null == temp){
        // 说明剩余未交换节点只有一个，不足以交换
        break;
    }

    fast.setNext(temp.getNext());
    slow.setNext(temp);
    temp.setNext(fast);

    // 更新指针，注意交换后的位置
    slow = fast;
    fast = (SimpleLinkedNode) fast.getNext();
    index += 2;
}

对最开始的两个节点进行判断，此时，slow表示第一个节点，fast表示第二个节点。（如果此时设置了虚拟头节点，就不需要对此进行特殊判断了）。

1
2
3
4
5
6
7
8
9
10
11
12
13
if(1 == index){
    temp = (SimpleLinkedNode) fast.getNext();

    slow.setNext(temp);
    fast.setNext(slow);

    head = fast;

    // 更新指针，fast直接指向temp，slow不需要改变，因为交换后的slow就是temp的前一个。
    fast = temp;
    index++;

}

总体代码如下所示：

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
public static void reverseListByTwo(SimpleLinkedList sll){

    SimpleLinkedNode head = sll.getHeaad();

    SimpleLinkedNode fast = (SimpleLinkedNode) head.getNext();
    SimpleLinkedNode slow = head;
    SimpleLinkedNode temp;

    int index = 1;  // 用于保存当前slow指针所在的位置，fast始终在slow指针的下一位

    // 当有两个节点时
    while(fast != null){

        // 对于开始两个节点需要特殊判断
        if(1 == index){
            temp = (SimpleLinkedNode) fast.getNext();

            slow.setNext(temp);
            fast.setNext(slow);

            head = fast;

            // 更新指针，fast直接指向temp，slow不需要改变，因为交换后的slow就是temp的前一个。
            fast = temp;
            index++;

        }else if(index % 2 == 0){

            temp = (SimpleLinkedNode) fast.getNext();

            if(null == temp){
                break;
            }

            fast.setNext(temp.getNext());
            slow.setNext(temp);
            temp.setNext(fast);

            // 更新指针
            slow = fast;
            fast = (SimpleLinkedNode) fast.getNext();
            index += 2;
        }
    }

    // 输出最后结果
    temp = head;
    while(temp.hasNext()){
        System.out.print(temp.getValue() + "-->");
        temp = (SimpleLinkedNode) temp.getNext();
    }

    System.out.println(temp.getValue() + ".");

}

试着优化一下，发现其实两两交换之后的slow和fast指针的位置刚好满足下一个交换的位置，所以index不必判断，只需要判断头两个节点即可。

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
public static void reverseListByTwo(SimpleLinkedList sll){

    SimpleLinkedNode head = sll.getHeaad();

    SimpleLinkedNode fast = (SimpleLinkedNode) head.getNext();
    SimpleLinkedNode slow = head;
    SimpleLinkedNode temp;

    int index = 1;  // 用于保存当前slow指针所在的位置，fast始终在slow指针的下一位

    // 当有两个节点时
    while(fast != null){

        // 对于开始两个节点需要特殊判断
        temp = (SimpleLinkedNode) fast.getNext();

        if(1 == index){

            slow.setNext(temp);
            fast.setNext(slow);

            head = fast;

            // 更新指针，fast直接指向temp，slow不需要改变，因为交换后的slow就是temp的前一个。
            fast = temp;
            index++;

        }else{

            if(null == temp){
                break;
            }

            fast.setNext(temp.getNext());
            slow.setNext(temp);
            temp.setNext(fast);

            // 更新指针
            slow = fast;
            fast = (SimpleLinkedNode) fast.getNext();
        }
    }

    // 输出最后结果
    temp = head;
    while(temp.hasNext()){
        System.out.print(temp.getValue() + "-->");
        temp = (SimpleLinkedNode) temp.getNext();
    }

    System.out.println(temp.getValue() + ".");

}

参考代码随想录中的方法，设置虚拟头结点，关键部分仍然不变，保留两节点的前一个节点slow，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
31
32
33
34
public static void reverseByTwo(SimpleLinkedList sll){

    // 设置虚拟节点
    SimpleLinkedNode dummyNode = new SimpleLinkedNode("dummyNode");
    dummyNode.setNext(sll.getHeaad());

    SimpleLinkedNode slow = dummyNode;
    SimpleLinkedNode fast = (SimpleLinkedNode) dummyNode.getNext();
    SimpleLinkedNode temp = (SimpleLinkedNode) fast.getNext();

    while(temp != null){

        fast.setNext(temp.getNext());
        slow.setNext(temp);
        temp.setNext(fast);

        slow = fast;
        fast = (SimpleLinkedNode) fast.getNext();
        if(fast != null){
            temp = (SimpleLinkedNode) fast.getNext();
        }else{
            temp = null;
        }
    }

    // 输出
    temp = (SimpleLinkedNode) dummyNode.getNext();
    while(temp.hasNext()){
        System.out.print(temp.getValue() + "-->");
        temp = (SimpleLinkedNode) temp.getNext();
    }

    System.out.println(temp.getValue() + ".");
}

测试代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {

    SimpleLinkedNode sln = new SimpleLinkedNode("Hello");

    SimpleLinkedList sll = new SimpleLinkedList(sln);

    sll.addTail(new SimpleLinkedNode("world"));
    sll.addTail(new SimpleLinkedNode("My"));
    sll.addTail(new SimpleLinkedNode("name"));
    sll.addTail(new SimpleLinkedNode("is"));
    sll.addTail(new SimpleLinkedNode("zhang"));
    sll.addTail(new SimpleLinkedNode("san"));
    sll.addTail(new SimpleLinkedNode("well"));

    sll.getValue();

    //        reverseLinkedList(sll);

    //        reverseListByTwo(sll);
    reverseByTwo(sll);
}

2.3 删除建表的倒数第N个节点（经典）

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

DSAA_019.png (765×334) (gitee.io)

在不知道链表长度的前提下，这道题一个简单的思路是，先遍历一遍获取链表的长度，然后再遍历一遍删除指定节点。显示需要扫描两次。实现代码如下：

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
public static void delNodeByIndex(SimpleLinkedList sll, int index){

    int length = 0;
    SimpleLinkedNode dummyNode = new SimpleLinkedNode("dummyNode");    // 虚拟头节点
    dummyNode.setNext(sll.getHeaad());

    SimpleLinkedNode temp = (SimpleLinkedNode) dummyNode.getNext();

    while(temp != null){
        length++;
        temp = (SimpleLinkedNode) temp.getNext();
    }

    temp = dummyNode;

    for (int i = 0; i < length - index; i++) {
        temp = (SimpleLinkedNode) temp.getNext();
    }

    if(((SimpleLinkedNode) temp.getNext()).hasNext()){
        // 说明删除的不是尾结点
        temp.setNext(((SimpleLinkedNode) temp.getNext()).getNext());

    }else{
        // 删除的是尾结点
        temp.setNext(null);
    }

    // 输出
    temp = (SimpleLinkedNode) dummyNode.getNext();
    if(temp == null){
        System.out.println();
        return;
    }
    while(temp.hasNext()){
        System.out.print(temp.getValue() + "-->");
        temp = (SimpleLinkedNode) temp.getNext();
    }

    System.out.println(temp.getValue() + ".");
}

那么如何遍历一次解决该问题呢？关键在于如何找到这个节点，换句话说，如何知道当前节点距离尾结点的距离，如果这个距离为N，那么这个节点就是要删除的节点。

可以提前设置好两个指针slow和fast，指针之间的距离为N，slow和fast同时向后移动。当fast指针到达尾结点的时候，说明slow指针指向的节点为倒数第N个节点。

实现代码如下所示：

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
public static void delNodeByTwoPointer(SimpleLinkedList sll, int index){

    // 设置虚拟头节点
    SimpleLinkedNode head = new SimpleLinkedNode("dummyNode");
    head.setNext(sll.getHeaad());

    SimpleLinkedNode slow = head;
    SimpleLinkedNode fast = head;

    // 移动，形成slow和fast之间的距离
    int distance = 0;
    while(distance < index){
        fast = (SimpleLinkedNode) fast.getNext();
        distance++;
    }

    // 向后遍历
    while(fast.hasNext()){
        fast = (SimpleLinkedNode) fast.getNext();
        slow = (SimpleLinkedNode) slow.getNext();
    }

    // fast到达末尾，此时slow的下一个就是要删除的节点
    slow.setNext(((SimpleLinkedNode) slow.getNext()).getNext());

    // 输出删除后的链表
    SimpleLinkedNode sln = (SimpleLinkedNode) head.getNext();
    while(sln.hasNext()){
        System.out.print(sln.getValue() + "-->");
        sln = (SimpleLinkedNode) sln.getNext();
    }
    System.out.println(sln.getValue() + ".");

}

2.4 链表相交

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例 1：

输入：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]

输出：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 个节点。

**这道题的描述不正确，[leetcode原题链接](面试题 02.07. 链表相交 - 力扣（LeetCode） (leetcode-cn.com))**，二者只要有相交节点，那么相交节点之后的节点均相交。

DSAA_020.png (742×241) (gitee.io)

这道题要看原题描述，原题中的解释示例的输入有问题，参考代码随想录中的思路。两条链表尾部相同，那么较长的链表的头部一定不可能相交；二者相交的长度最长是较短的链表的长度，并且不会错位。所以可以直接将长链表的指针移动到短链表的长度处开始一一比较。

DSAA_021.png (729×461) (gitee.io)

代码实现如下所示：

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
public static void interSectPlus(SimpleLinkedList sll1, SimpleLinkedList sll2){
    SimpleLinkedNode sln1 = sll1.getHeaad();
    SimpleLinkedNode sln2 = sll2.getHeaad();

    // 获取长度
    int length1 = 0, length2 = 0;

    while (sln1 != null){
        length1++;
        sln1 = (SimpleLinkedNode) sln1.getNext();
    }

    while (sln2 != null){
        length2++;
        sln2 = (SimpleLinkedNode) sln2.getNext();
    }

    // sln1指针指向较长的链表，sln2指向较短的链表
    if(length1 >= length2){
        sln1 = sll1.getHeaad();
        sln2 = sll2.getHeaad();
    }else{
        sln1 = sll2.getHeaad();
        sln2 = sll1.getHeaad();
    }

    // 将指针移动到需要比较的位置
    for (int i = 0; i < Math.abs(length1 - length2); i++) {
        sln1 = (SimpleLinkedNode) sln1.getNext();
    }

    // 开始比较
    while(sln1 != null){
        if(sln1.equals(sln2)){
            System.out.println("二者开始相交的位置：" + sln1.getValue());
            break;
        }
        sln1 = (SimpleLinkedNode) sln1.getNext();
        sln2 = (SimpleLinkedNode) sln2.getNext();
    }
}

2.5 环形链表II（经典，太难了，没有完全理解）

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

DSAA_022.png (1158×878) (gitee.io)

既然链表中存在环，那么一定是在尾结点处指向了其入环的第一个节点。因为其他位置的节点的指针一定指向了下一个节点，否则之后的节点就不会出现在链表中了。所以直接遍历到最后一个节点，判断其指针的指向即可。因为存在环，所以无法根据指针是否为空来判断该节点是否是尾结点，实际上既然存在环，就说明没有了尾节点，所有不能通过这种方法来判断。

参考代码随想录中的思路，先判断是否有环，再判断环的入口。

判断链表是否有环

可以使用快慢指针法， 分别定义fast和slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点。如果没有环的话，fast指针用于在slow的前面，二者永远不会相遇。而如果fast和slow指针在途中相遇，说明这个链表有环。

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢？

首先第一点： 如果有环，fast指针一定先进入环中，此后指针肯定不会出环，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。

那么来看一下，为什么fast指针和slow指针一定会相遇呢？

可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。

DSAA_023.png (706×222) (gitee.io)

fast和slow各自再走一步， fast和slow就相遇了

这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

动画如下：

DSAA_024.gif (568×402) (gitee.io)

找到环的入口

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

DSAA_025.png (918×294) (gitee.io)

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

1
(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

动画如下：

DSAA_026.gif (572×414) (gitee.io)

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

实现代码如下：

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
public class LinkedListTest07 {

    public static void main(String[] args) {
        SimpleLinkedNode head = new SimpleLinkedNode("Hello");
        SimpleLinkedList sll = new SimpleLinkedList(head);

        SimpleLinkedNode mid = new SimpleLinkedNode("world");

        sll.addTail(mid);
        sll.addTail(new SimpleLinkedNode("my"));
        sll.addTail(new SimpleLinkedNode("name"));

        SimpleLinkedNode tail = new SimpleLinkedNode("is");
        sll.addTail(tail);

        tail.setNext(tail);
//        tail.setNext(new SimpleLinkedNode("asdf"));

        SimpleLinkedNode result = findFirstCycleNode(sll);

        System.out.println(result == null ? null : result.getValue());

    }


    public static SimpleLinkedNode findFirstCycleNode(SimpleLinkedList sll){

        SimpleLinkedNode head = sll.getHeaad();

        SimpleLinkedNode slow = head;
        SimpleLinkedNode fast = head;

        SimpleLinkedNode index1, index2;

        while(fast != null){
            fast = (SimpleLinkedNode) fast.getNext();
            if(fast != null){
                fast = (SimpleLinkedNode) fast.getNext();
                slow = (SimpleLinkedNode) slow.getNext();

                // 有环
                if(slow == fast){

                    index1 = fast;
                    index2 = head;
                    while(index1 != index2){
                        index1 = (SimpleLinkedNode) index1.getNext();
                        index2 = (SimpleLinkedNode) index2.getNext();
                    }
                    return index1;
                }
            }
        }

        return null;
    }
}

这道题有点难，不是很理解。待复习…

3. 备注

部分参考代码随想录 (programmercarl.com)。

文章作者: 浮云
文章链接: https://ihianian.github.io/2021/10/16/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-04-%E9%93%BE%E8%A1%A8/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
数据结构与算法
赏
  目录