《算法通关村第一关——链表青铜挑战笔记》

《算法通关村第一关——链表青铜挑战笔记》

Java如何构造出链表

概念

如何构造出链表，首先必须了解什么是链表！

单向链表就像一个铁链一样，元素之间相互链接，包含多个节点，每个节点有一个指向后继元素的next指针。表中最后一个元素的next指向null。

链表的核心是一个节点只能有一个后继节点，但不代表链表指向本节点的只有一个。

Java与C++不同没有了指针，只有引用，不用进行内存的回收，会使得代码的书写更加简单。

Java如何编写链表

先放代码

package AlgorithmFirst;

public class LinkedNode {
    private int data;
    private LinkedNode next;
    public LinkedNode(int data){
        this.data = data;
    }

    /**
     * 获取数据
     * @return 数据值
     */
    public int getData(){
        return this.data;
    }

    /**
     * 设置数据的值
     * @param data 数据
     */
    public void setData(int data){
        this.data = data;
    }

    /**
     * 获取下一个节点
     * @return 当前节点的下一个几点
     */
    public LinkedNode getNext(){
        return this.next;
    }

    /**
     * 设置下一个节点的值
     * @param next 下一个节点
     */
    public void setNext(LinkedNode next){
        this.next = next;
    }

    /**
     * 获取链表长度
     * @param head 头节点
     * @return
     */
    public static int getListLength(LinkedNode head){
        int length = 0 ;
        LinkedNode node = head;
        while(node != null){
            length ++ ;
            node = node.next;
        }
        return length;
    }

    /**
     * 缺省位置，直接在最后插入
     *
     * @param head       头节点
     * @param insertNode 插入节点
     * @return 头节点
     */
    public static LinkedNode insertNode(LinkedNode head, LinkedNode insertNode) {
        int size = getListLength(head);
        // return insertNode(head,insertNode,size+1); 修改一下，以便insertNode后面的元素能够全部插入进来。
        int count = 1;
        LinkedNode temp = head;
        if (head == null) {
            return insertNode;
        }
        while (temp != null) {
            if (count == size) {
                temp.next = insertNode;
                temp = null;
            } else {
                temp = temp.next;
                count++;
            }
        }
        return head;
    }

    /**
     * 指定位置插入
     * @param head 头节点
     * @param nodeInsert 插入节点
     * @param position 插入位置，从1开始
     * @return 返回头节点
     */
    public static LinkedNode insertNode(LinkedNode head , LinkedNode nodeInsert, int position){
        if (head == null ){
            // 如果head == null 表示当前链表为空，可以直接返回当前节点，或者报异常，这里直接把它当作头节点。
            return nodeInsert;
        }
        // 已经存在的元素的个数
        int size = getListLength(head);
        if(position > size + 1 || position < 1 ){
            System.out.println("位置参数越界");
            return head;
        }

        // 表头插入
        if(position == 1 ){
            nodeInsert.next = head;
            // 这里可以直接 return nodeInsert
            head = nodeInsert;
            return head;
        }

        LinkedNode pNode = head;
        int count = 1;
        // 这里position 被上面的size限制住了，不用考虑pNode = null
        while(count < position -1){
            pNode = pNode.next;
            count ++ ;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;
        return head;
    }

    /**
     * 缺省参数的删除最后一个节点
     * @param head 链表头节点
     * @return 返回新链表头节点
     */
    public static LinkedNode deleteNode(LinkedNode head){
        int size = getListLength(head);
        return deleteNode(head,size);
    }

    /**
     * 根据位置删除节点
     * @param head 链表头节点
     * @param position 位置从1开始，最大链表大小 超出不删除，返回原头节点。
     * @return 新链表头节点
     */
    public static LinkedNode deleteNode(LinkedNode head , int position){
        if(head == null) {
            // 链表为空，无法删除
            return null ;
        }
        int size = getListLength(head);
        if(position > size || position < 1 ){
            System.out.println("输入参数有误" );
            return head;
        }
        if( position == 1){
            return head.next;
        }else{
            LinkedNode cur = head;
            int count = 1;
            while(count<position-1){
                cur = cur.next;
                count ++;
            }
            LinkedNode curNode = cur.next;
            cur.next = curNode.next;
            //上面两行可以简化成 ： cur.next = cur.next.next
        }
        return head;
    }

    public static void  printLinkedList(LinkedNode head){
        int count = 0;
        while(head != null){
            System.out.println("第 "+ ++count +" 个："+ head.data);
            head = head.next;
        }
    }

    public static void main(String[] args) {
        LinkedNode head = new LinkedNode(0);
        for(int i = 0 ; i<10 ; i++){
            head = LinkedNode.insertNode(head,new LinkedNode(i+1));
        }
        System.out.println("origin:");
        printLinkedList(head);
        head = deleteNode(head,3);
        System.out.println("delete the third ");
        printLinkedList(head);
        head = deleteNode(head);
        System.out.println("delete the last one");
        printLinkedList(head);
        head = insertNode(head,new LinkedNode(11));
        System.out.println("insert one from last");
        printLinkedList(head);
        head = insertNode(head,new LinkedNode(22222),1);
        System.out.println("insert to first");
        printLinkedList(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
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
193
194
195

添加节点需要注意的点

链表无节点

如果开始链表无节点，那么就把插入的节点作为头节点返回

插入到头节点

注意一下插入进行的操作步骤，首先把插入节点的 next 等于 head ， 然后再让head 等于 插入节点，然后返回。

插入到结尾

插入到结尾需要从head 遍历到结尾，然后用最后一个节点的next指向插入节点即可。

插入到中间

插入到中间，需要注意先通过遍历，找到要插入位置的前一个，然后插入节点的next等于前一个的next，而前一个的next指向插入节点。一定要注意顺序！

删除节点需要注意的

链表为空

直接返回

删除头节点

直接返回头节点的next 节点就好了。

删除中间节点、尾节点

首先要找到中间节点的前一个节点，让前一个节点的next指向自己的next的next就可以了。

近期在自学 Java 做项目，加入了一个编程学习圈子，里面有编程学习路线和原创的项目教程，感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑，也希望能对大家有帮助，扫 ⬇️ 二维码即可加入。

也可以点击链接：我正在「编程导航」和朋友们讨论有趣的话题，你⼀起来吧？