Java中的链表_java链表

前言

上一节中，我们讲过了Java中的ArrayList，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。

一、链表

1.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序来实现的。类似于火车一样。

注意：

1. 链式结构在逻辑上是连续的，但是在物理上不一定连续
2. 现实中的结点一般都是在堆上申请出来的
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

实际中，链表的结构多种多样，一下情况组合起来就有8种链表结构：

1. 单向或者双向
   

2. 带头或者不带头
   

3. 循环或者非循环
   

虽然有这么多的链表结构，但是我们重点讲解两种：

• 无头单向非循环链表：结构简单，一般不会单独用来存储数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
• 无头双向链表：在java集合框架中LinkedList底层实现就是无头双向循环链表。

1.2 链表的实现

SingleLinkedList类
1

// 1、无头单向非循环链表实现
public class SingleLinkedList {

    class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node head;

    public void createLinkList() {
        Node node1 = new Node(12);
        Node node2 = new Node(45);
        Node node3 = new Node(88);
        Node node4 = new Node(92);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
    }

    //打印链表
    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        Node cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int size() {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

    //尾插法
    public void addLast(int data) {
        Node node = new Node(data);

        if (head == null) {
            head = node;
        }

        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) throws ListIndexOutofException {
        if (index < 0 || index > size()) {
            throw new ListIndexOutofException("index位置不合法");
        }
        if (index == 0) {
            addFirst(data);
        }
        if (index == size()) {
            addLast(data);
        }

        int count = 0;
        Node cur = head;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }

        Node node = new Node(data);
        node.next = cur.next;
        cur.next = node;

    }



    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        Node cur = searchprev(key);
        if(cur == null) {
            return;
        }
        Node del = cur.next; //要删除的节点
        cur.next = del.next;
    }

    /*
    查找key前一个节点
     */
    private Node searchprev(int key) {
        Node cur = head;
        while (cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null; //没有删除的节点
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        Node pre = head;
        Node cur = head.next;
        while (cur != null) {
            if(cur.val==key) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        if(head.val==key) {
            head = head.next;
        }
    }

    public void clear() {
        head = 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
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

ListIndexOutofException类
1

public class ListIndexOutofException extends RuntimeException {
    public ListIndexOutofException() {
    }

    public ListIndexOutofException(String message) {
        super(message);
    }
}

1
2
3
4
5
6
7
8
9

Test类
1

public class Test {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.createLinkList();
        singleLinkedList.display();
        System.out.println(singleLinkedList.contains(12));
        System.out.println(singleLinkedList.size());

        singleLinkedList.addFirst(8); //头插
        singleLinkedList.display();

        singleLinkedList.addLast(9);//尾插
        singleLinkedList.display();

        singleLinkedList.addIndex(2,999);
        singleLinkedList.addIndex(4,999);
        singleLinkedList.display();

        singleLinkedList.remove(88);
        singleLinkedList.display();

        singleLinkedList.removeAllKey(999);
        singleLinkedList.display();
    }
}

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

二、链表面试题

以下是我要讲解的5个关于链表的面试题，包含OJ链接。

2.1 判定链表是否是回文

题目：链表的回文结构

思路： 由于链表是单向的，所以我们如果要使用双指针的思想解决该题，就需要将后半部分数据的指向进行逆置。也就是

	1——>2——>2<——1
1

要实现后半部分的逆置，我们需要找到链表的中间节点 。在链表的实现里，我们已经使用快慢指针找到链表的中间节点。最后我们再使用双指针，遍历链表，比较前后对称节点的值是否相等。

代码实现：

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if(head == null) {
            return false;
        }
        if(head.next == null) {
            return true;
        }
        //快慢指针找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //翻转后半部分的指向
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        while(slow != head) {
            if(slow.val != head.val) {
                return false;
            }
            //下面这个if语句是用来判断链表长度为偶数的情况的
            if(head.next == slow) {
                return true;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;

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

2.2 合并两个有序链表

题目：合并两个有序链表

思路： 要返回一个新的升序链表，那么我们需要申请一个新的头节点，然后通过遍历两个链表，并将其值进行对比，值小的，则添加进新的头节点，并且头节点和值小的链表都往后移动，这样一直比较下去，直到一个链表比较完为止。如果最后还有一个链表不为null，那么直接添加进新的头节点。

代码实现：

/**
 * 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 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(0);//申请新的头节点
        ListNode cur = newHead; //使用cur来间接使用新的头节点
        //循环的条件是两个链表都不为null
        while(list1 != null && list2 != null) {
            if(list1.val<list2.val) {
                cur.next =  list1;
                list1 = list1.next; //往后走
                cur = cur.next; //往后走
            }else {
                cur.next =  list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        //如果哪个链表不为null，则直接添加进新的头节点
        if(list1!=null) {
            cur.next = list1;
        }
        if(list2!=null) {
            cur.next =list2;
        }
        return newHead.next; //返回新头节点的后面部分，因为newHead.val为0
    }
}
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

2.3 获取链表倒数第K个节点

题目：链表中倒数第K个节点

思路： 这道题也是一道数学题，我们仍然使用快慢指针的思想，让fast先走k-1步，然后让slow和fast一起走。知道fast.next为null。

代码实现：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    	//判断K值的合法性以及head是否为null
        if(k <= 0 || head==null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(k-1 != 0) {
            fast = fast.next;
            //这个if语句处理了当k值大于链表长度的情况，复杂度变低
            if(fast == null) {
                return null;
            }
            k--;
        }
        while(fast.next != 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
23
24
25
26
27
28
29
30
31
32
33

2.4 获取链表的中间节点

题目：链表的中间节点

**思路：**快慢指针，让fast的速度是slow的两倍,走完之后，slow指向的节点就是中间节点。

代码实现：

/**
 * 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 {
    public ListNode middleNode(ListNode head) {
        if(head==null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        //两个循环条件不能交换位置，不然空指针异常
        while(fast!=null && fast.next!=null) {
            fast = fast.next.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
23
24
25

2.5 单链表的逆置

题目：反转链表

思路： 使用头插法将后面的节点一个一个插在前面。

代码实现：

/**
 * 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 {
    public ListNode reverseList(ListNode head) {
        if(head==null) {
            return null;
        }
        if(head.next==null) {
            return head;
        }
        ListNode cur = head.next; 
        head.next = null; //修改为null
        
        while(cur!=null) {
            ListNode curNext = cur.next; //一定要保存cur.next，因为cur在改变
            cur.next = head;  //修改cur的指向，指向原本的头节点
            head = cur; //改变头节点，cur成为新的头节点
            cur = curNext; //改变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

总结

以上就是今天要讲的内容，本文仅仅简单介绍了链表的使用以及几个面试题，链表在Java数据结构中非常重要，学习时要多与数学结合起来，多画图，多思考！