avatar
主页
计算机
金融
数学
关于
本站文章数 :
188
本站总字数 :
1364.7K
已运行天数 :
Kaka Wan Yifan
主页
计算机
金融
数学
关于
2.数组、链表
计算机算法入门经典(Java与Python描述)
字数总计:6.1K

算法和数据结构的关系

如果要讨论算法，就无法避免的讨论数据结构。
为什么？
这得从算法和数据结构的关系讲起了

这得从算法和数据结构的关系讲起了

举个例子，蛋炒饭。要做蛋炒饭，我们需要热锅、倒油、打蛋等，这些就是算法，而米饭、鸡蛋、油、盐就是数据结构。
我们除了掌握各种算法之外，还需要掌握数据结构。
否则，就像这张图。
隔夜饭

那么，到底什么是数据结构呢？
数据结构(Data Structure)是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。
数据结构通常可分为4类。

  1. 线性结构
    线性结构是最简单的数据结构，包括数组、链表，以及由它们衍生出来的栈、队列、哈希表。
  2. 树
    树是相对复杂的数据结构，其中比较有代表性是二叉树，由它又衍生出了二叉堆之类的数据结构。
  3. 图
    图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。
  4. 其他数据结构
    除上述所列的几种基本数据结构以外，还有一些其他的千奇百怪的数据结构。它们由基本数据结构变形而来，用于解决某些特定问题，如跳表、哈希链表、位图等。

数据结构和算法是相辅相成的。
数据结构是为算法服务的，算法要作用在特定的数据结构之上。

现在，我们开始讨论数据结构。

数组的定义

我们讨论的第一个数据结构是数组。
为什么数组从0开始编号

为什么数组从0开始编号？

要回答这个问题，我们先来讨论一下什么是数组。
数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
这里有两个核心点。

  1. 线性表
  2. 连续的内存空间和相同类型的数据

线性表

首先，什么是线性表？
线性表(Linear List)，顾名思义，就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。常见的线性表，除了数组外，还有之后会讨论的链表、队列、栈等。
线性表

与线性表相对立的概念是非线性表，比如二叉树、堆、图等。在非线性表中，其特点是数据之间并不是简单的前后关系。
非线性表

连续的内存空间和相同类型的数据

这是一个"一箭双雕"的特点，既有弊，又有利。
弊：插入和删除非常的低效
利：读取非常的高效

对于插入和删除

比如，现在有a、b、c、d、e，一共5个元素。现在我们要在2这个位置插入一个元素x。
我们需要怎么做？
首先，我们需要把把c、d和e都依次往后移动，把第二个位置腾出来，然后把x放进去。也就是说，数组中插入一个元素的话，可能会导致数组中所有的元素都要移动位置。删除也是同样的道理。
那么，如果数组的长度就是5，我们还要再插入一个元素呢？
理论上这个是没法做的，但如果一定要这么做，也不是没有办法。
数组容器，我们很快就会讨论这个。

对于读取

对于读取，那这个就很好办了。
你不是连续的内存空间吗？你不是相同类型的数据吗？
相同类型的数据就意味着每一个元素做占用的内存空间是一致的。
比如，int[] a = new int[10]，第一个元素的内存空间是100到103，那么我们要找第三个元素，怎么找？108到111，就是第三个元素。

数组的寻址

在讨论线性表、连续的内存空间和相同类型的数据这两个特点后，我们终于可以回答为什么数组从0开始编号了。
因为"线性表"，所以数组中的元素只有前后关系；又因为"连续的内存空间和相同类型的数据"；我们可以得到数组寻址公式如下：

a[i]Address=baseAddress+i∗dataTypeSize\text{a[i]Address} = \text{baseAddress} + \text{i} * \text{dataTypeSize}

有没有发现什么？
我们要找数组中的第一个元素，i的值是多少？0。第二个元素呢？i的值是1。
所以，所谓的"下标"，可以理解成"偏移(offset)"。a[0]就是偏移为0的位置，也就是首地址；a[k]就表示偏移k个type_size的位置。
这就是为什么数组从0开始编号。

数组容器

数组和数组容器

现在，我们来做一件事情。我们定义一个数组，赋值，打印。

示例代码：

1
2
3
4
5
6
7
8
9
10
// 初始化一个长度为5的ArrayList
ArrayList<Integer> a = new ArrayList<Integer>(5);
a.add(1);
a.add(2);
a.add(3);
a.add(4);
a.add(5);
System.out.println(a);
a.add(6);
System.out.println(a);

运行结果：

1
2
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]

示例代码：

1
2
3
4
a = [1, 2, 3, 4, 5]
print(a)
a.append(6)
print(a)

运行结果：

1
2
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]

这个好像不对啊？说好的长度是5，怎么还把第6个元素加进去了呢？
一定是打开方式不对

来，我们换一下。

示例代码：

1
2
3
4
5
6
7
8
9
int[] a = new int[5];
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
System.out.println(Arrays.toString(a));
a[5] = 6;
System.out.println(a);
运行结果： 
1
2
3
4
[1, 2, 3, 4, 5]
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
	at ch02.TestArray.func2(TestArray.java:34)
	at ch02.TestArray.main(TestArray.java:10)

示例代码：

1
2
3
4
5
6
7
8
9
a = [None] * 5
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 4
a[4] = 5
print(a)
a[5] = 6
print(a)
运行结果： 
1
2
3
4
5
[1, 2, 3, 4, 5]
Traceback (most recent call last):
  File "/Users/kaka/Documents/algorithm-data-structures-for-blog/Python/ch02/TestArray.py", line 13, in <module>
    a[5] = 6
IndexError: list assignment index out of range

看！报错了吧！报错就对了。

在Java中，我们用的ArrayList，就不是数组，而是数组容器。
那，Python呢？在Python中，我们用的那玩意就不叫数组，是List。(也是容器的一种)

实现一个数组容器

现在，我们来实现一个数组容器。
那我们实现哪些方法？
数组容器方法

  • 除了那个remove(Object o)，因为我们在我们这里index和element都是int类型，没法实现。

示例代码：

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
package ch02;

/**
 * 我的数组容器
 */
public class MyArrayList {

    // 用来存储容器中的元素
    private int[] array;
    // 容器中元素的个数
    private int size;

    /**
     * 构造方法
     * @param capacity 初始化大小
     */
    public MyArrayList(int capacity) {
        this.array = new int[capacity];
        size = 0;
    }

    /**
     * 在制定位置新增元素
     * @param index 制定的位置
     * @param element 元素
     * @throws Exception 数组越界异常
     */
    public void add(int index, int element) throws Exception {

        //判断访问下标是否超出范围
        if(index<0 || index>size){
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }

        //如果实际元素达到数组容量上线，数组扩容
        if(size >= array.length){
            resize();
        }

        //从右向左循环，逐个元素向右挪一位。
        for(int i=size-1; i>=index; i--){
            array[i+1] = array[i];
        }

        //腾出的位置放入新元素
        array[index] = element;

        size++;
    }

    /**
     * 在最近的一个空位添加元素
     * @param element 元素
     * @throws Exception
     */
    public void add(int element){
        //如果实际元素达到数组容量上线，数组扩容
        if(size >= array.length){
            resize();
        }

        //腾出的位置放入新元素
        array[size] = element;

        size++;
    }

    /**
     * 数组扩容
     */
    public void resize(){
        // 扩大到原来大小的两倍
        int[] arrayNew = new int[array.length*2];
        //从旧数组拷贝到新数组
        System.arraycopy(array, 0, arrayNew, 0, array.length);
        array = arrayNew;
    }

    /**
     * 在指定位置删除元素
     * @param index 制定位置
     * @return 被删除的元素
     * @throws Exception
     */
    public int remove(int index) throws Exception {
        //判断访问下标是否超出范围
        if(index<0 || index>=size){
            throw new IndexOutOfBoundsException("超出数组实际元素范围！");
        }

        int deletedElement = array[index];
        //从左向右循环，逐个元素向左挪一位。
        for(int i=index; i<(size-1); i++){
            array[i] = array[i+1];
        }
        size--;

        return deletedElement;
    }



    /**
     * 输出数组
     */
    public void output(){
        String rnt = "";
        for (int i = 0; i < size; i++) {
            rnt = rnt + array[i] + " ";
        }
        System.out.println(rnt);
    }

    public static void main(String[] args) throws Exception {
        MyArrayList myArrayList = new MyArrayList(3);
        myArrayList.add(0,1);
        myArrayList.add(1,2);
        myArrayList.add(2,3);
        myArrayList.output();
        myArrayList.add(4);
        myArrayList.add(5);
        myArrayList.add(6);
        myArrayList.output();
        myArrayList.remove(1);
        myArrayList.remove(1);
        myArrayList.remove(1);
        myArrayList.output();
    }
}

运行结果：

1
2
3
1 2 3 
1 2 3 4 5 6 
1 5 6

示例代码：

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
# 我的数组容器
class MyArrayList:
    def __init__(self, capacity):
        """

        :param capacity: 长度
        """
        self.array = [None] * capacity
        self.size = 0

    def add_index_element(self, index, element):
        """
        在指定位置添加元素
        :param index: 指定位置
        :param element: 元素
        :return:
        """
        # 判断访问下标是否超出范围
        if index < 0 or index > self.size:
            raise Exception("超出数组实际元素范围！")
        # 如果实际元素达到数组容量上线，数组扩容
        if self.size >= len(self.array):
            self.resize()
        # 从右向左循环，逐个元素向右挪一位。
        for i in range(self.size - 1, index - 1, -1):
            self.array[i + 1] = self.array[i]
        # 腾出的位置放入新元素
        self.array[index] = element
        self.size += 1

    def add_element(self, element):
        """
        在尾部放入新元素
        :param element: 放在尾部的元素
        :return:
        """
        # 如果实际元素达到数组容量上线，数组扩容
        if self.size >= len(self.array):
            self.resize()
        # 在尾部放入新元素
        self.array[self.size] = element
        self.size += 1

    def add(self, *args):
        """
        add
        :param args:
        :return:
        """
        if len(args) == 2:
            self.add_index_element(index=args[0], element=args[1])
        if len(args) == 1:
            self.add_element(element=args[0])

    def resize(self):
        """
        数组扩容
        :return:
        """
        array_new = [None] * len(self.array) * 2
        # 从旧数组拷贝到新数组
        for i in range(self.size):
            array_new[i] = self.array[i]
        self.array = array_new

    def remove(self, index):
        """
        移除指定位置的数组
        :param index: 指定的位置
        :return:
        """
        # 判断访问下标是否超出范围
        if index < 0 or index >= self.size:
            raise Exception("超出数组实际元素范围！")
        # 从左到右，逐个元素向左挪动一位
        for i in range(index, self.size-1):
            self.array[i] = self.array[i + 1]
        self.size -= 1

    def output(self):
        """
        输出数组
        :return:
        """
        print(self.array[:self.size])


myArrayList = MyArrayList(3)
myArrayList.add(0, 1)
myArrayList.add(1, 2)
myArrayList.add(2, 3)
myArrayList.output()
myArrayList.add(4)
myArrayList.add(5)
myArrayList.add(6)
myArrayList.output()
myArrayList.remove(1)
myArrayList.remove(1)
myArrayList.remove(1)
myArrayList.output()
运行结果： 
1
2
3
[1, 2, 3]
[1, 2, 3, 4, 5, 6]
[1, 5, 6]

链表的结构

正如我们之前的讨论，数组的优点是读取快，缺点是插入和删除慢。
现在有一个数据结构，它的优点就是数组的缺点，而它的缺点也就是数组的优点。
链表。
链表读取慢，但是插入和删除快。

除了这两点不同外，数组和链表还有一个不同的地方。数组要求是在内存中的连续空间，而链表却可以是内存中的离散空间。
数组和链表

链表有很多种，有单链表、循环链表、双向链表还有双向循环链表。
这些链表我们都会讨论。
从单链表开始。

单链表

单链表

如图，就是单链表的结构。每一个节点除了存储数据之外，还记录下一个节点的地址。通过这种方法，把离散的内存空间串联起来。
但有两个节点不太一样。
最后一个节点，它的next指向的是NULL。
第一个节点，没有任何指针指向它，这个节点也被称为头节点。有了头节点，我们可以遍历得到整个链表。

这个像什么？
带鱼咬尾巴，一钓一大串。

那么，为什么链表读取很慢，但是增加和删除很快？
关于读取慢，我想这个很好解释。我们要从头节点开始，通过一个又一个的指针，才能读取到我们想要的内容。比如，我们要读取链表的第N个数字，那么我们就需要N-1个指针，一个又一个的指过去，才能读取到第N个数字。而在数组中，通过数组寻址，一步到位。

那么，为什么增加和删除很快呢？
来看看增加和删除的方法。
链表的增加和删除

比如，在b和c之间，我们想插入一个节点x，在数组中，我们需要先把c及c之后的节点都后移，有多少个就需要后移多少个；通过这个方法，把位置空出来，再把x放进去。但在链表中，把b的指针从指向c改成指向x，再把x的指针指向c，搞定！
对于删除，在数组中，如果我们要在把b节点删除，我们需要把c及c之后的节点都前移，有多少个就需要前移动多少个。而在链表中，把a节点从指向b改成指向c，再把b节点中指向c的指针断开。
为什么要把b的指针断开？如果不断开？
乱了，乱了，乱了

乱了，乱了，乱了。
这样的话，我们可以把b节点作为头节点，然后遍历得到之后的所有数据。

其实，还有一个问题，这是题外话。就算我们把两个指针断开了，b节点不是还在吗？b节点本身不处理吗？这就是所谓的高级语言的高级之处了，自动化的垃圾回收机制，被删除的节点会被自动回收。

其他链表结构

关于其他类型的链表，我想我们用图就可以表示清楚了。

循环链表

循环链表

双向链表

双向链表

双向循环链表

双向循环链表

链表容器

熟悉Java的同学们都知道，在Java中，除了有ArrayList，还有LinkedList。顾名思义，LinkedList是基于链表的List。
现在，我们来实现一个LinkedList。

实现这些方法。
LinkedList

  • 除了remove(Object o)
  • 其中remove()是remove第一个节点

示例代码：

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
package ch02;

/**
 * 我的LinkedList
 */
public class MyLinkedList {

    /**
     * 链表节点
     */
    private static class Node {
        // 节点的值
        int data;
        // next
        Node next;

        /**
         * 构造方法
         * @param data
         */
        Node(int data) {
            this.data = data;
        }
    }

    //链表的头节点指针
    private Node head;
    //链表的尾节点指针
    private Node last;
    //链表实际长度
    private int size;

    /**
     * 构造方法
     */
    public MyLinkedList() {
        // 一个空的List
    }

    /**
     * get方法
     * @param index
     * @return index位置的节点
     * @throws Exception
     */
    public Node get(int index) throws Exception {
        if (index<0 || index>=size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node temp = head;
        for(int i=0; i<index; i++){
            temp = temp.next;
        }
        return temp;
    }


    /**
     * add方法
     * @param index
     * @param element
     * @throws Exception
     */
    public void add(int index, int element) throws Exception {

        if (index<0 || index>size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }

        Node insertedNode = new Node(element);
        if(size == 0){
            //空链表
            head = insertedNode;
            last = insertedNode;
        } else if(index == 0){
            //插入头部
            insertedNode.next = head;
            head = insertedNode;
        }else if(size == index){
            //插入尾部
            last.next = insertedNode;
            last = insertedNode;
        }else {
            //插入中间
            Node prevNode = get(index-1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        size++;
    }

    /**
     * 在尾部添加节点
     * @param element
     * @throws Exception
     */
    public void add(int element) throws Exception{
        Node insertedNode = new Node(element);

        //插入尾部
        last.next = insertedNode;
        last = insertedNode;

        size++;
    }


    /**
     * remove
     * @param index
     * @return 被删除的节点
     * @throws Exception
     */
    public Node remove(int index) throws Exception {
        if (index<0 || index>=size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node removedNode = null;
        if(index == 0){
            //删除头节点
            removedNode = head;
            head = head.next;
            if(size == 1){
                last = null;
            }
        }else if(index == size-1){
            //删除尾节点
            Node prevNode = get(index-1);
            removedNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        }else {
            //删除中间节点
            Node prevNode = get(index-1);
            Node nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        size--;
        return removedNode;
    }

    /**
     * remove第一个节点
     * @return
     * @throws Exception
     */
    public Node remove() throws Exception{
        if (size < 1) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node removedNode = head;
        head = head.next;
        if(size == 1){
            last = null;
        }
        size--;
        return removedNode;
    }

    /**
     * 输出链表
     */
    public void output(){
        String rnt = "";
        Node temp = head;
        while (temp!=null) {
            rnt = rnt + temp.data + " ";
            temp = temp.next;
        }
        System.out.println(rnt);
    }

    public static void main(String[] args) throws Exception {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.add(0,1);
        myLinkedList.add(1,2);
        myLinkedList.add(2,3);
        myLinkedList.output();
        myLinkedList.remove();
        myLinkedList.remove();
        myLinkedList.output();
        myLinkedList.add(4);
        myLinkedList.add(5);
        myLinkedList.add(6);
        myLinkedList.output();
        myLinkedList.remove(1);
        myLinkedList.remove(1);
        myLinkedList.output();
        System.out.println(myLinkedList.get(1).data);
    }
}

运行结果：

1
2
3
4
5
1 2 3 
3 
3 4 5 6 
3 6 
6

示例代码：

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
# 我的链表容器

# 链表的节点
class Node:
    def __init__(self, data):
        """

        :param data:
        """
        self.data = data
        self.next = None


class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head = None
        self.last = None

    def get(self, index):
        """
        获取指定位置的节点
        :param index:
        :return:
        """
        if index < 0 or index >= self.size:
            raise Exception("超出链表节点范围！")
        p = self.head
        for i in range(index):
            p = p.next
        return p

    def add_data(self, element):
        """
        在尾部添加节点
        :param element:
        :return:
        """
        node = Node(element)
        # 插入尾部
        self.last.next = node
        self.last = node
        self.size += 1

    def add_index_element(self, element, index):
        """
        在指定位置添加节点
        :param element:
        :param index:
        :return:
        """
        if index < 0 or index > self.size:
            raise Exception("超出链表节点范围！")
        node = Node(element)
        if self.size == 0:
            # 空链表
            self.head = node
            self.last = node
        elif index == 0:
            # 插入头部
            node.next = self.head
            self.head = node
        elif self.size == index:
            # 插入尾部
            self.last.next = node
            self.last = node
        else:
            # 插入中间
            prev_node = self.get(index - 1)
            node.next = prev_node.next
            prev_node.next = node
        self.size += 1

    def add(self, *args):
        """
        添加节点
        :param args:
        :return:
        """
        if len(args) == 2:
            self.add_index_element(index=args[0], element=args[1])
        if len(args) == 1:
            self.add_data(element=args[0])

    def remove_head(self):
        """
        移除头部节点
        :return:
        """
        removed_node = self.head
        self.head = self.head.next
        if self.size == 1:
            self.last == Node
        self.size -= 1
        return removed_node

    def remove_index(self, index):
        """
        移除指定位置的节点
        :param index:
        :return:
        """
        if index < 0 or index >= self.size:
            raise Exception("超出链表节点范围！")
        # 暂存被删除的节点，用于返回
        if index == 0:
            # 删除头节点
            removed_node = self.head
            self.head = self.head.next
            if self.size == 1:
                self.last == Node
        elif index == self.size - 1:
            # 删除尾节点
            prev_node = self.get(index - 1)
            removed_node = prev_node.next
            prev_node.next = None
            self.last = prev_node
        else:
            # 删除中间节点
            prev_node = self.get(index - 1)
            next_node = prev_node.next.next
            removed_node = prev_node.next
            prev_node.next = next_node
        self.size -= 1
        return removed_node

    def remove(self, *args):
        """

        :param args:
        :return:
        """
        if len(args) == 1:
            self.remove_index(args[0])
        if len(args) == 0:
            self.remove_head()

    def output(self):
        rnt = []
        p = self.head
        while p is not None:
            rnt.append(p.data)
            p = p.next
        print(rnt)


myLinkedList = MyLinkedList()
myLinkedList.add(0, 1)
myLinkedList.add(1, 2)
myLinkedList.add(2, 3)
myLinkedList.output()
myLinkedList.remove()
myLinkedList.remove()
myLinkedList.output()
myLinkedList.add(4)
myLinkedList.add(5)
myLinkedList.add(6)
myLinkedList.output()
myLinkedList.remove(1)
myLinkedList.remove(1)
myLinkedList.output()
print(myLinkedList.get(1).data)

运行结果：

1
2
3
4
5
[1, 2, 3]
[3]
[3, 4, 5, 6]
[3, 6]
6

链表中的快慢指针

现在提一个问题，我们如何获取链表的中间节点。
这个很简单，size除以2，就是中间节点的index，然后就从头节点开始遍历，轻松搞定？
不是这样的。
size只在LinkedList容器中有，如果这是链表，哪里有size？
那怎么办？
那我们先把整个链表都遍历一遍，获取链表的size，然后size除以2，再遍历一遍。这样的话，我们需要的遍历次数是

size+size2\text{size} + \frac{\text{size}}{2}

现在，我们换一个思路。我们先用一个两倍速度的快指针遍历一遍，比如需要遍历N次，然后在用慢指针遍历N次。这样慢指针是不是恰好在中间的位置。这样的话，我们需要的遍历次数是

size2+size2\frac{\text{size}}{2} + \frac{\text{size}}{2}

大致思路就是这样的。有几个细节还需要捋一捋。
快慢指针

这里解释一下：

  • 只要快指针还能往下走，就继续往下走。
    • 所以在图中偶数次的情况，fastTimes = 2
    • 所以在图中奇数次的情况，fastTImes = 3
  • 当快指针遍历结束时，其next节点不为空，说明有链表的size是偶数个，这时候中间节点有两个
  • 当快指针遍历结束时，其next节点为空，说明链表的size是奇数个，这时候中间节点只有一个

示例代码：

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
package ch02;

/**
 * 快慢指针，中间节点
 */
public class LinkedListMid {

    /**
     * 链表节点
     */
    private static class Node {
        // 节点的值
        int data;
        // next
        Node next;

        /**
         * 构造方法
         * @param data
         */
        Node(int data) {
            this.data = data;
        }
    }

    /**
     * 获取中间节点
     * @param head head节点
     * @return 中间节点列表，可能存在多个中间节点，所以是list。
     */
    public static String getLinkedListMid(Node head){

        String rnt = "";

        // head == null   没有节点，自然没有中间节点，返回null
        if (head == null){
            return null;
        }

        // 如果前面的没命中，链表不为空

        // 先让快指针开始跑
        Node fastNode = head;
        int fastTimes = 0;
        // 只要fastNode的next的next不是空，就说明还可以进行遍历。
        // 为了避免fateNode.next就是空，导致空指针异常，先判断fastNode的next
        while (null != fastNode  && null != fastNode.next && null != fastNode.next.next){
            // 遍历
            fastNode = fastNode.next.next;
            // 次数加一
            fastTimes = fastTimes + 1;
        }


        // 然后慢指针
        Node midNode = head;
        for (int i = 0; i < fastTimes; i++) {
            midNode = midNode.next;
        };
        rnt = rnt + midNode.data;

        // 奇数偶数特殊处理
        // 如果fastNode的next不为空，说明是偶数个节点，那么中间节点就有两个。
        // 否则，奇数个节点，中间节点只有一个。
        if (fastNode.next != null){
            rnt = rnt + " " + midNode.next.data;
        }

        return rnt;
    }

    public static void main(String[] args) {
        String midNode = "";

        Node test = null;
        System.out.print("当链表为空，中间节点是   ");
        System.out.print(getLinkedListMid(test));
        System.out.print("\n");

        test = new Node(1);
        midNode = getLinkedListMid(test);
        System.out.print("当链表长度为1，中间节点是   ");
        System.out.print(midNode);
        System.out.print("\n");

        test = new Node(1);
        test.next = new Node(2);
        midNode = getLinkedListMid(test);
        System.out.print("当链表长度为2，中间节点是   ");
        System.out.print(midNode);
        System.out.print("\n");

        test = new Node(1);
        test.next = new Node(2);
        test.next.next = new Node(3);
        test.next.next.next = new Node(4);
        test.next.next.next.next = new Node(5);
        test.next.next.next.next.next = new Node(6);
        midNode = getLinkedListMid(test);
        System.out.print("当链表长度为6，中间节点是   ");
        System.out.print(midNode);
        System.out.print("\n");


        test = new Node(1);
        test.next = new Node(2);
        test.next.next = new Node(3);
        test.next.next.next = new Node(4);
        test.next.next.next.next = new Node(5);
        test.next.next.next.next.next = new Node(6);
        test.next.next.next.next.next.next = new Node(7);
        midNode = getLinkedListMid(test);
        System.out.print("当链表长度为7，中间节点是   ");
        System.out.print(midNode);
        System.out.print("\n");

    }

}

运行结果：

1
2
3
4
5
当链表为空，中间节点是   null
当链表长度为1，中间节点是   1
当链表长度为2，中间节点是   1 2
当链表长度为6，中间节点是   3 4
当链表长度为7，中间节点是   4

示例代码：

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
# 链表的节点
class Node:
    def __init__(self, data):
        """

        :param data:
        """
        self.data = data
        self.next = None


def getLinkedListMid(head):
    """
    获取中间节点
    :param head: 链表的head
    :return: 中间节点
    """
    rnt = []

    if None == head:
        return None

    # 如果前面的没有命中，说明链表不为空

    # 先让快指针开始跑
    fastNode = head
    fastTimes = 0
    # 只要fastNode的next的next不是空，就说明还可以进行遍历。
    # 为了避免fateNode.next就是空，导致空指针异常，先判断fastNode的next
    while (fastNode is not None) and (fastNode.next is not None) and (fastNode.next.next is not None):
        # 遍历
        fastNode = fastNode.next.next
        # 次数加一
        fastTimes = fastTimes + 1

    # 然后慢指针
    midNode = head
    for i in range(fastTimes):
        midNode = midNode.next

    rnt.append(midNode)

    # 奇数偶数特殊处理
    # 如果fastNode的next不为空，说明是偶数个节点，那么中间节点就有两个。
    # 否则，奇数个节点，中间节点只有一个。
    if fastNode.next is not None:
        rnt.append(midNode.next)

    return rnt


if __name__ == '__main__':
    test = None
    print('当链表为空，中间节点是   ', getLinkedListMid(test))

    test = Node(1)
    midNodeList = getLinkedListMid(test)
    print('当链表长度为1，中间节点个数是   ', len(midNodeList), '   中间节点是   ', midNodeList[0].data)

    test = Node(1)
    test.next = Node(2)
    midNodeList = getLinkedListMid(test)
    print('当链表长度为2，中间节点个数是   ', len(midNodeList), '   中间节点是   ', midNodeList[0].data, ',', midNodeList[1].data)

    test = Node(1)
    test.next = Node(2)
    test.next.next = Node(3)
    test.next.next.next = Node(4)
    test.next.next.next.next = Node(5)
    test.next.next.next.next.next = Node(6)
    midNodeList = getLinkedListMid(test)
    print('当链表长度为6，中间节点个数是   ', len(midNodeList), '   中间节点是   ', midNodeList[0].data, ',', midNodeList[1].data)

    test = Node(1)
    test.next = Node(2)
    test.next.next = Node(3)
    test.next.next.next = Node(4)
    test.next.next.next.next = Node(5)
    test.next.next.next.next.next = Node(6)
    test.next.next.next.next.next.next = Node(7)
    midNodeList = getLinkedListMid(test)
    print('当链表长度为7，中间节点个数是   ', len(midNodeList), '   中间节点是   ', midNodeList[0].data)

运行结果：

1
2
3
4
5
当链表为空，中间节点是   null
当链表长度为1，中间节点是   1
当链表长度为2，中间节点是   1 2
当链表长度为6，中间节点个数是   3 4
当链表长度为7，中间节点个数是   4

关于链表，还有一类问题是链表反转。这个我们放在讨论递归的时候再进行讨论。因为链表反转本身的确没啥用，但却是一个很好的递归算法实践。

文章作者: Kaka Wan Yifan
文章链接: https://kakawanyifan.com/10602
版权声明: 本博客所有文章版权为文章作者所有，未经书面许可，任何机构和个人不得以任何形式转载、摘编或复制。
留言板