java数据结构 --- 链表

顺序表适合查找操作,不适合频繁的插入和删除操作
链表的分类可以根据单向或者双向,是否循环,有无头节点,共有2^3,及8种
链表在逻辑上连续,在物理上不连续

1. 初识链表(不带头节点的单向非循环链表)

1.1 链表的创建

public class LinkList {
    class Link{
        int val;
        Link add;
        public Link(int val){
            this.val = val;
        }
    }
    //头节点
    Link link;
    public void creat(){
       Link link1 = new Link(45);
       Link link2 = new Link(49);
       Link link3 = new Link(89);
       Link link4 = new Link(60);
       Link link5 = new Link(90);

        this.link = link1;
        link1.add = link2;
        link2.add = link3;
        link3.add = link4;
        link4.add = link5;
        link5.add = null;
    }
    public static void main(String[] args) {
        LinkList linklist = new LinkList();
        linklist.creat();
    }
}
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

1.2 链表的功能实现

    public void display(){
    //保持头节点位置不变,定义一个头结点的傀儡,代替头节点跑腿
       Link re = this.link;
      //判断re是否为空
       while(re!= null){
           System.out.print(re.val + " ");
           //使re指向下一个结点
           re = re.add;
       }
    }
1
2
3
4
5
6
7
8
9
10

需要注意遍历链表时while函数括号中并不是(re.next != null),而是(re != null).

1.2.1 遍历链表

    public int size(){
        Link re = this.link;
        int i = 0;
        while(re != null){
            i++;
            re = re.add;
        }
        return i;
    }
1
2
3
4
5
6
7
8
9

1.2.2 判断链表中是否包含某元素

    public boolean contions(int n){
        Link re = this.link;
        while(re != null){
            if (n == re.val){
                return true;
            }
            re = re.add;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10

1.2.3 头插法

    public void addFirst(int data){
        Link add = new Link(data);
        add.add = this.link;
        link = add;
    }
1
2
3
4
5

1.2.4 尾插法

    public void addLast(int data){
        Link re = this.link;
        Link add = new Link(data);
        if(re == null){
            this.link = add;
        }else{
            while(re.add != null){
                re = re.add;
            }
            re.add = add;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

1.2.5 任意下标插入

    public void addIndex(int index, int date){
        if (index < 0 | index > size() - 1){
            new IndexwrongException("任意下标插入异常");
        }
        if (index == 0){
            addFirst(date);
            return;
        }
        if(index == size() - 1){
            addLast(date);
            return;
        }
        Link add = new Link(date);
        Link re = this.link;
        int i = 0;
        while(i < index - 1){
            re = re.add;
            i++;
        }
        add.add = re.add;
        re.add = add;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.2.6 删除元素

public void remove(int date){
        if (link == null){
            return ;
        }
        if(this.link.val == date){
            this.link = this.link.add;
            return;
        }
        Link rem = find(date);
        if(rem == null){
            System.out.println("没有该元素");
        }else{
            rem.add = rem.add.add;
        }
    }
    private Link find(int date){
        Link re = this.link;
        while(re.add != null){
            if (re.add.val == date){
                return re;
            }
            re = re.add;
        }
        return 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

---

---

---

---

1.2.7 删除的数字有多个且要全部删除

    public void removeAllKey(int date){
        if (node == null){
            return ;
        }
        Node re1 = node;
        Node re2 = node.next;
        while(re2 != null){
            if(re2.val == date){
                re1.next = re2.next;
                re2 = re2.next;
            }else{
                re1 = re2;
                re2 = re2.next;
            }
        }
        if (node.val == date){
            node = node.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意最后的if函数中不要写成node = re1,因为re1不一定是node.next

1.3 二刷链表代码

package danlianbiao;

class LinkedList{
    static class Node{
        int valu = 0;
        Node next = null;
        public Node(int valu){
            this.valu = valu;
        }
    }
    Node node0 = null;
    int size = 0;
    void creatList(){
        Node node1 = new Node(99);
        Node node2 = new Node(89);
        Node node3 = new Node(67);
        Node node4 = new Node(34);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node0 = node1;
        this.size = 4;
    }
    void display(){
        Node eg = this.node0;
        while(eg != null){
            System.out.print(eg.valu + "  ");
            eg = eg.next;
        }
        System.out.println();
    }
    void headadd (int val){
        Node node = new Node(val);
        node.next = node0;
        node0 = node;
        this.size++;
    }
    void tailadd(int val){
        Node node = new Node(val);
        Node eg = this.node0;
        if(this.size != 0){
            while(eg.next != null){
                eg = eg.next;
            }
            eg.next = node;
        }else{
            this.node0 = node;
        }
        this.size++;
    }
    void add ( int pos, int val) throws IllegalLocation{
        if (pos < 0 || pos >this.size){
            throw new IllegalLocation("pos位置不合法");
        }else if(pos == 0){
            headadd(val);
        }else if (pos == this.size){
            tailadd(val);
        }else{
            Node node = new Node(val);
            Node eg = this.node0;
            while(pos - 1 != 0){
                eg = eg.next;
                pos--;
            }
            node.next = eg.next;
            eg.next = node;
            this.size++;
        }
    }
    boolean contain(int val){
        Node eg = this.node0;
        while(eg != null){
            if(eg.valu == val)
                return true;
            eg = eg.next;
        }
        return false;
    }
    void remove(int val){
        if(this.node0 == null){
            System.out.println("删除失败, 此链表为空");
            return;
        }
        Node eg = this.node0;
//          if(eg.valu == val){
//              eg = eg.next;
//              this.size--;
//              return;
//        }
//注意:删除的元素为链表中第一个元素时,不能用eg操作,用node0;
        if(this.node0.valu == val){
            this.node0 = this.node0.next;
            this.size--;
            return;
        }
        while(eg.next != null){
            if (eg.next.valu == val){
                eg.next = eg.next.next;
                this.size--;
                return;
            }
            eg = eg.next;
        }
        System.out.println("删除失败,链表中没有该元素");
    }
    void removeall(int val){
        if (this.size == 0){
            System.out.println("删除失败,该链表为空");
            return;
        }
        Node eg1 = this.node0;
        Node eg2 = this.node0.next;
        while(eg2 != null){
            if (eg2.valu == val){
                eg1.next = eg2.next;
                eg2 = eg2.next;
                this.size--;
            }else{
                eg1 = eg2;
                eg2 = eg2.next;
            }
        }
        if(this.node0.valu == val){
            node0 = node0.next;
            this.size--;
        }
    }
    void clean(){
        this.node0 = null;
        this.size = 0;
    }
}



public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.creatList();
        //System.out.println("size = " + list.size);
        list.headadd(100);
        list.display();
        list.headadd(100);
        list.tailadd(100);
        list.tailadd(46);
        list.display();
        //System.out.println("size = " + list.size);
        try{
            list.add(0, 100);
            //System.out.println("size = " + list.size);
            list.add(9, 340);
            //System.out.println("size = " + list.size);
            list.add(10,78 );
            //System.out.println("size = " + list.size);
            list.add(4, 100);
            System.out.println("size = " + list.size);
        }catch(IllegalLocation e){
            e.printStackTrace();
        }
        list.display();
        list.remove(450);
        list.display();
        list.remove(78);
        list.display();
        list.remove(100);
        list.display();
        list.remove(1000);
        System.out.println("size = " + list.size);
        list.removeall(100);
        list.display();
        System.out.println("size = " + list.size);
        System.out.println(list.contain(100));
        System.out.println(list.contain(1000));
        //list.disList();
        list.clean();
        list.display();
        System.out.print("size = " + list.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
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

2. 链表题目

2.1 旋转链表(置换链表)

//置换单链表
    Node disList(){
        if(this.node0 == null){
            return null;
        }else if (this.node0.next == null){
            return this.node0;
        }else{
            Node eg1 = this.node0.next;
            this.size = 1;
            this.node0.next = null;
            while(eg1 != null){
                Node eg2 = eg1.next;
                headadd(eg1.valu);
                eg1 = eg2;
            }
        }
        return this.node0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.2 获取链表中间节点(快慢指针)

    //获取链表中间元素
    Node getmidlist(){
        if (this.node0 == null){
            System.out.println("获取失败,该线性表为空");
            return null;
        }else if (this.size == 1){
            System.out.println("获取成功,该线性表只有一个元素");
            return this.node0;
        }else{
            Node fast = this.node0;
            Node slow = this.node0;
            while((fast != null) && (fast.next != null)){
            //注意这里必须先是fast!=null在前,否则可能会空指针异常
                fast = fast.next.next;
                slow = slow;
            }
            return slow;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.3 获取倒数第k个节点

    //获取倒数第k个节点
    Node getbackwards(int k){
        if ((k <= 0)){
            System.out.println("获取失败, 要获取位置不合法");
            return null;
        }
        if (this.node0 == null){
            System.out.println("获取失败,链表为空");
        }
        Node fast = this.node0;
        Node slow = this.node0;
        while (fast.next != null){
            while(k - 1 != 0){
                fast = fast.next;
                k--;
                if (fast.next == null){
                    System.out.println("获取失败, 要获取位置不合法");
                    return null;
                }
            }
            slow = slow.next;
            fast = fast.next;
        }
        System.out.println("获取成功");
        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

2.4 有序合并两个有序链表

    Node mergelists(Node node1, Node node2){
        Node newnode = new Node(0);
        Node eg = newnode;
        while((node1 != null) && (node2 != null)){
            if (node1.valu < node2.valu){
                eg.next = node1;
                node1 = node1.next;
                eg = eg.next;

            }else{
                eg.next = node2;
                node2 = node2.next;
                eg = eg.next;
            }
        }
        if (node1 != null){
            eg.next = node1;
        }else{
            eg.next = node2;
        }
        return newnode.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.5 链表分割 (血的教训)

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if (pHead == null) {
            return null;
        }
        ListNode eg = pHead;
        ListNode ea1 = null;
        ListNode es1 = null;
        ListNode ea2 = null;
        ListNode es2 = null;
        while (eg != null) {
            if (eg.val < x) {
                if (ea1 == null) {
                    ea1 = eg;
                    es1 = eg;
                } else {
                    es1.next = eg;
                    es1 = es1.next;
                }
                eg = eg.next;
            } else {
                if (ea2 == null) {
                    ea2 = eg;
                    es2 = eg;
                } else {
                    es2.next = eg;
                    es2 = es2.next;
                }
                eg = eg.next;
            }
        }
        if (ea1 == null) {
            return ea2;
        }
        es1.next = ea2;
        if (ea2 != null) {
            es2.next = null;
        }
        return ea1;
    }
}
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

这道题值得注意的细节在于在执行es2.next = null;之前必须判断ea2是不是为空,否则可能会报空指针异常
血的教训

2.6 链表指定区间反转(遍历一次)

一下午的心血

    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        if (m == n) {
            return head;
        }
        ListNode eg = head;
        for (int i = 1; i < m - 1; i++) {
            eg = eg.next;
        }
        ListNode eg1 = null;
        if(head.next.next == null){
            eg1 = eg.next;
            eg.next = null;
            eg1.next = eg;
            head = eg1;
            return head;
        }
        if(m == 1){
            eg1 = eg;
        }else{
           eg1 = eg.next;
        }
        ListNode eg2 = eg1.next;
        ListNode eg4 = eg1;
        eg.next = null;
        eg1.next = null;
        while ((n - m) != 0) {
            ListNode eg3 = eg2.next;
            eg2.next = eg1;
            eg1 = eg2;
            eg2 = eg3;
            n--;

        }
        if (m == 1){
            eg4.next = eg2;
            return eg1;
        }
        eg4.next = eg2;
        eg.next = eg1;
        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
44
45
46
47
48

2.7 判断回文链表

需要注意的点在于

注意这里判断条件不能写成slow.next != null,而是eg1.next ! null

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        //找中间节点
        if (A == null){
            return false;
        }
        if(A.next == null){
            return true;
        }
        ListNode fast = A;
        ListNode slow = A;
        while((fast != null) && (fast.next != null)){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode eg1 = slow.next;
        while(eg1 != null){
        //注意这里判断条件不能写成slow.next != null;
            ListNode eg2 = eg1.next;
            eg1.next = slow;
            slow = eg1;
            eg1 = eg2;
        }
        ListNode eg3 = A;
        while(eg3 != slow){
            if(eg3.val != slow.val){
                return false;
            }
            if (eg3.next == slow){
                return true;
            }
            eg3 = eg3.next;
            slow = slow.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

2.8 相交链表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
     if(headA == null || headB == null){
         return null;
     }
     ListNode eg1 = headA;
     ListNode eg2 = headB;
    while(eg1 != eg2){
    eg1 = (eg1 == null)? headB: eg1.next;
    eg2 = (eg2 == null)? headA: eg2.next;
     }
     return eg1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.9 判断是否有环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if (head == null){
            return null;
        }
        //len记录链表长度
        int len = 0;
        //eg用于遍历链表
        ListNode eg = head;
        while (eg != null){
             len++;
             eg = eg.next;
        }
        if (len < k){
        //如果长度小于k,返回当前链表
            return head;
        }
        int num = len / k;
        //ListNode用于标记每一组的第一个节点
        ListNode headeg = head;
        //eg用于记录每一组翻转后的最后一个节点
        eg = head;
        for (int i = 1; i <= num; i++){
        //为每一组的翻转做准备工作
            ListNode eg0 = headeg;
            ListNode eg1 = headeg.next;
            headeg.next = null;
            int egi = k;
            while(egi - 1!= 0){
            //对每一组进行翻转
                egi--;
                ListNode eg2 = eg1.next;
                eg1.next = headeg;
                headeg = eg1;
                eg1 = eg2;
            }
            if (i == 1){
   //移动头节点,使其指向翻转后的第一个节点,只能在第一次翻转时执行一次
                head = headeg;
            }else{
       //连接翻转后的前一组与翻转后的当前组
                eg.next = headeg;
                eg = eg0;
            }
            //连接翻转后的当前组与下一组
            eg0.next = eg1;
            //使headeg始终指向下一组的头节点
            headeg = eg1;
        }
       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
44
45
46
47
48
49
50
51

2.11 链表中环的入口结点

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null){
            return null;
        }
        ListNode fast = pHead, slow = pHead;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if (fast == null || fast.next == null){
            return null;
        }
        slow = pHead;
        while (slow != fast){
            slow = slow.next;
            fast = fast.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