【数据结构】单链表实现_数据结构单链表的实现

链表

顺序表的缺点就是当插入或删除元素时，可能会涉及大量元素的移动，并且在添加元素时，可能会造成空间浪费，所以又出现了另外一种数据结构 — 链表结构。

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接实现的，由结点（或节点）组成，结构如下：

注意：

1. 链式结构在逻辑上是连续的，物理上不一定连续。
2. 结点一般是从堆上申请的。
3. 两次申请的空间可能连续，也可能不连续。

实际中的链表结构有很多种，例如：单向或双向、带头或不带头、循环或非循环，通过组合就可以达到 8 种链表结构。

单向结构或双向结构：

---

带头或不带头：

---

循环或非循环：

---

通过组合可以得到 8 种：单向带头循环、单向带头非循环、单向不带头循环、单向不带头非循环、还剩四种把单向改成双向即可，但是我们只用掌握 不带头单向非循环 和 不带头双向非循环 即可，只要掌握这两种，其他结构的操作方法都类似。

实现不带头单向非循环链表

☞☞☞ 不带头单向非循环链表实现：

首先定义一个单链表类：这里的头结点只是用来指向链表中的第一个节点，相当于C语言中的指针，而带头结点的链表中，头结点是一个真正的结点，头结点中的 val 域可以存放表长信息或者不存储信息，而 next 部分则存放第一个节点的地址。

public class MySingleList {
   static class ListNode  {
        public int val;       //存储的数据
        public ListNode  next;//存储下一结点的地址

        public ListNode (int val) {
            this.val = val;
        }
    }
    public ListNode head;   //代表当前链表的头结点的引用

}
1
2
3
4
5
6
7
8
9
10
11
12

定义好单链表后，我们创建一个单链表。

打印单链表的方法：

//创建单链表
public void createLink() {
    ListNode node1 = new ListNode(11);
    ListNode node2 = new ListNode(22);
    ListNode node3 = new ListNode(33);
    ListNode node4 = new ListNode(44);
    //让结点指向结点，形成链表
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    //头结点指向第一个节点
    head = node1;
}

//打印单链表
public void display() {
//生成一个新结点，否则在遍历时，head移动后就找不到链表的头了。
    ListNode cur = head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    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

先看运行结果：

执行过程：

打印单链表过程：

---

判断单链表是否包含关键字 key：

运行结果：

---

求单链表的长度：

//单链表的长度
public int size() {
    ListNode cur = head;
    int count = 0;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}
1
2
3
4
5
6
7
8
9
10

运行结果：

---

头插法：

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
1
2
3
4
5
6

先看运行结果：

头插实现过程：

---

尾插法：

//尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    //如果链表里没有结点,那新结点就是头结点
    if (head == null) {
        head = node;
        return;
    }
    ListNode cur = head;
    //找到最后一个结点
    while (cur.next != null) {
        cur = cur.next;
    }
    //让最后一个结点指向新结点
    cur.next = node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行结果：

尾插实现过程：

---

任意位置插入，第一个数据节点为 0 号下标：

//任意位置插入
public void addIndex(int index, int data) {
	//检查插入的位置是否合法
    checkIndex(index);
    //如果在下标0位置插入，就相当于头插
    if (index == 0) {
        addFirst(data);
        return;
    }
    //如果下标和链表的长度一样，就相当于尾插
    if (index == size()) {
        addLast(data);
        return;
    }
    //其他情况：找到index前一个位置
    ListNode cur = head;
    while (index - 1 > 0) {
        cur = cur.next;
        index--;
    }
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = 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

运行结果：

任意位置插入实现过程：

---

删除第一次出现关键字为 key 的结点：

//删除第一次出现关键字为key的结点
public void remove(int key) {
    //如果head为空，直接返回
    if (head == null) {
        return;
    }
    //如果head的值就为key，只需让head指向下一个结点
    if (head.val == key) {
        head = head.next;
    }
    //找到值等于key的前一个结点
    ListNode cur = searchPre(key);
    //判断返回来的结点是否为空
    if (cur==null){
        return;
    }
    //修改指向
    cur.next=cur.next.next;
}

private ListNode searchPre(int key) {
    ListNode cur = head;
    //遍历到最后一个节点
    while (cur.next != null) {
        //如果下一节点的值等于key的话就返回当前节点
        if (cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    //链表遍历完也没有key就返回null
    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
26
27
28
29
30
31
32
33

运行效果：

remove 实现过程：

---

实现删除所有值为 key 的节点：

public void removeAllkey(int key) {
    if (head == null) {
        return;
    }
    //指向前一节点
    ListNode prev = head;
    //指向当前节点
    ListNode cur = head.next;
    //遍历
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        } else {
            prev = cur;
            cur = cur.next;
        }
    }
    //此时只有头结点没有判断是否等于key，等于就指向下一结点
    if (head.val == key) {
        head = head.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：

实现过程：

动图演示：

---

清空链表方法：

public void clear() {
	//只需让头结点置为null即可
    head = null;
}
1
2
3
4

以上就是单链表的基本实现，而 删除所有值为 key 的节点 方法的实现也是力扣上面的题目 ☛☛☛[移除链表元素]

链表题目

反转链表

下面再来一道代码题加深对单链表的操作： ☛☛☛ Leetcode — 反转链表。

题目要求：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

反转前的链表：11 -> 22 -> 33 -> 44

反转后的链表：44 -> 33 -> 22 -> 11

我们可能会想遍历到最后，再将其指向前一个结点，直到第一个节点，但这是单链表，不是双链表，只知道下一个结点，不知道上一个结点。所以我们在遍历的同时，采用头插法将每个结点插入到链表的头部完成链表反转。

代码：

public ListNode reverseList(ListNode head) {
	//如果链表为空，返回null
    if(head == null){
        return null;
    }
    //只有一个节点
    if(head.next == null){
        return head;
    }
    	//让 cur 指向头结点的下一个结点
        ListNode cur = head.next;
        //将 head 的next域置为 null
        head.next = null;
        //cur结点不为空 就继续
        while(cur != null){
        	//让curNext 指向cur节点的下一结点，防止到不到后面的结点
            ListNode curNext = cur.next;
            //将 cur 的next域指向 head
            cur.next = head;
            //head前移
            head = cur;
            //cur找到剩余的结点，继续反转
            cur = curNext;
        }
        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

链表的中间结点

题目链接：链表的中间结点。
题目要求：

对于这题，我们使用的是快慢指针，快的走两步，慢的走一步，两个同时走，当快的走到终点时，慢的才走了一半，此时慢指针指向的就是链表的中间结点。

public ListNode middleNode(ListNode head) {
        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

奇数个结点链表和偶数个节点链表：

链表中倒数第k个结点

题目链接：链表中倒数第k个结点。
题目描述：

题目解析：

代码：

public ListNode FindKthToTail(ListNode head, int k) {
        //如果k小于0  或者链表为空返回null
        if (k < 0 || head == null)
            return null;

        //定义快慢指针
        ListNode fast = head;
        ListNode slow = head;

        //快指针走 k-1 步
        while (k - 1 != 0) {
            fast = fast.next;

            //如果 fast 为null，说明没有倒数k个节点
            if (fast == null)
                return null;
            k--;
        }

        //快指针走完 k-1 步后， 快慢同时走，快的走到链表最后，慢的就是倒数 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

合并两个有序链表

题目链接：合并两个有序链表。
题目描述：

实现过程：

代码：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode();
        ListNode tmp = newHead;
        while(list1 != null && list2 != null){
        //谁的值小，tmp 就指向谁，然后自己在往后
            if(list1.val < list2.val){
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }else{
                 tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            }
        }
        //谁不等于空，就等于谁
        if(list1 != null){
            tmp.next = list1;
        }
        if(list2 != null){
            tmp.next = list2;
        }
        //最后返回新结点的next即可
        return newHead.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

链表的回文结构

题目链接：链表的回文结构。
题目描述：

分析过程：

代码：

public boolean chkPalindrome(ListNode A) {
        if (A == null) {
            return false;
        }
        //只有一个节点也是回文结构
        if (A.next == null) {
            return true;
        }
        ListNode fast = A;
        ListNode slow = A;
        //找到中间结点，此时的中间结点就是slow
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //将中间结点后的结点反转，cur也走到了链表最后
        ListNode cur = slow;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //头结点A和最后节点slow不相遇，就继续进行判断
        while(A != slow){
            //只要值不等，就不是回文结构
            if(A.val != slow.val){
                return false;
            }
            //头结点的下一结点是 slow结点，也是回文
            if(A.next == slow){
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        //此时 结点A 和 结点slow 相遇，说明全程都是相等的，也就是回文结构，返回true
        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

CM11 链表分割

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

也就是原来是什么顺序，重新排列后还是什么顺序，只是把小于和大于 x 的结点分开了：

分析过程：

代码：

public ListNode partition(ListNode pHead, int x) {
        //bs 和 be 之间存放小于 x 的结点
        ListNode bs = null;
        ListNode be = null;
        //as 和 ae 之间存放大于等于 x 的结点
        ListNode as = null;
        ListNode ae = null;
        //从头结点开始遍历
        ListNode cur = pHead;
        while (cur != null) {
            //小于x的情况
            if (cur.val < x) {
                //小于x进来，判断当前是不是小于x的第一个节点
                if (bs == null) {
                //如果是第一个节点，bs 和 be都指向这个节点
                    bs = cur;
                    be = cur;
                } else {
                    //不是则使用尾插法添加数据
                    be.next = cur;
                    be = be.next;
                }
            } else {    //大于等于x的情况
                //同样判断是不是大于等于x的第一个节点，如果是第一个节点，as和bs都指向这个节点
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    //同样使用尾插法添加数据
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //不能保证有节点小于x，如果没有小于x的结点，返回大于x结点部分
        if (bs == null) {
            return as;
        }
        //如果能走到这里，说明有节点小于x，那就让小于x的最后一个结点和大于等于x的结点串起来
        be.next = as;

        if (as != null) {
            ae.next = null;
        }
        return bs;
    }
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

相交链表

题目链接：相交链表
题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。具体描述可点击链接查看。

分析过程：

代码：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //链表A的长度
        int lenA = 0;
        //链表B的长度
        int lenB = 0;
        ListNode pl = headA;
        ListNode ps = headB;
        while (pl != null){
            lenA++;
            pl = pl.next;
        }
        while (ps != null){
            lenB++;
            ps = ps.next;
        }
        //pl 和 ps指向已更改，需重新赋值
        pl = headA;
        ps = headB;
        //两个链表相差的个数
        int count = lenA - lenB;
        //如果count小于0，那么lenA个数就比lenB小，所以重新赋值，让pl指向的为两个链表中较长的一个
        //count也为正数
        if (count < 0){
            pl = headB;
            ps = headA;
            count = lenB - lenA;
        }
        //长的链表先走 count 步
        while (count != 0){
            pl = pl.next;
            count--;
        }
        //长的走完count步后，一起走直到相遇，或者在不相交时，两个都走到null退出
        while (pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        //相遇就是相交结点，其中一个为空，说明没有相交点，上面也走到了null
        return pl;
    }
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

环形链表

题目链接：环形链表
题目描述：给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。

例如：

分析过程：

代码：

public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!= null && fast.next != null){
            //fast走两步
            fast = fast.next.next;
            //slow走一步
            slow = slow.next;
            //相遇就是有环
            if (fast == slow)
                return true;
        }
        //退出说明fast为空，也就是没有环
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

环形链表 II

题目链接：环形链表 II
题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

例如：

分析过程：

代码：

public ListNode detectCycle(ListNode head) {
		//定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        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;
        }
        //其中一个指针回到起点
        fast = head;
        while(fast != slow){
        	//两个指针同时一步一步走
            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

以上就是单链表的实现以及牛客网和力扣上的一些关于链表的经典题目。