黑客灵魂

这个屌丝很懒，什么也没留下！

热门标签

数据结构——链表_遍历链表

作者：黑客灵魂 | 2024-07-13 03:17:20

踩

遍历链表

链表

概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

单向链表

思路分析

创建单向链表时，首先需要创建一个头节点，这个头节点不用来存储数据，当需要存储数据时，每添加一个数据则将前一个节点的next指向新加的数据即可。

遍历链表时，需要创建一个辅助变量，用来遍历整个链表。

代码实现

需求：添加员工，新添加的员工排在链表的最后面。

添加员工

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        EmpNode emp1 = new EmpNode(1, "mark");
        EmpNode emp2 = new EmpNode(2, "jack");
        EmpNode emp3 = new EmpNode(3, "marry");
        EmpNode emp4 = new EmpNode(4, "tom");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(emp1);
        singleLinkedList.add(emp2);
        singleLinkedList.add(emp3);
        singleLinkedList.add(emp4);

        singleLinkedList.list();
    }
}

class SingleLinkedList{
    //初始化添加头节点
    private EmpNode head = new EmpNode(0,"");
  
    public EmpNode getHead() {
        return head;
    }
  
    //添加节点：添加新数据到链表最后位置
    public void add(EmpNode newEmpNode){
        EmpNode temp = head;
        while (true){
            //找到链表的最后一个节点
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        temp.next = newEmpNode;
    }

    //显示链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
        }
        EmpNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

class EmpNode{
    public Integer id;
    public String name;
    public EmpNode next;

    public EmpNode() {
    }

    public EmpNode(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "EmpNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
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

现在我们要完成第二个需求，在添加时，按照id排序，也就是说，假如链表中有id为1和3的员工，这时候添加id为2的员工时需要插入到1，3之间，如果已有id为2的员工，返回提示信息无法添加。

顺序添加员工

思路分析：遍历所有的员工，这里temp指向id大于添加员工的id的前一个节点，有点绕口，举个例子，链表中有id为1和3的员工，这时候添加id为2的员工，我们的temp指向id为1的员工，将id为1的员工的next值赋值给新添加员工的next，再将id为1的员工next指向新添加员工。

    //顺序添加员工
    public void addById(EmpNode empNode){
        EmpNode temp= head;
        //用于记录是否已存在相同id的员工
        boolean flag = true;
        while (true){
            if (temp.next == null){
                break;
            }
            if (temp.next.id > empNode.id){
                //当查找的temp的下一个节点id大于插入的节点，则可以添加
                break;
            }else if (temp.next.id == empNode.id){
                //如果id相同，不能添加
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            empNode.next = temp.next;
            temp.next = empNode;
        }else {
            System.out.printf("编号为%d的员工已存在，无法添加",empNode.id);
        }
    }
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

节点的修改

既然是链表，用来存储数据，那么增删改查功能是必须具备的，接下来跟着小黄一起分析如何修改列表

需求：传入一个节点，根据员工id来修改员工的名称，如果没找到则返回提示信息

思路分析：借助辅助变量temp来遍历链表，如果找到id相同的则修改，不同则返回提示

    //修改员工信息
    public void update(EmpNode empNode){
        EmpNode temp = head;
        //用于记录是否查找到id相同的emp
        boolean flag = true;
        while (true){
            if (temp == null){
                flag = false;
                break;
            }
            if (temp.id == empNode.id){
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = empNode.name;
        }else {
            System.out.printf("您需要更新的id为%d的员工不存在\n",empNode.id);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

节点的删除

需求：传入一个员工id，删除该员工所在的节点

思路分析：借助辅助变量temp来遍历链表，这里要注意的是，我们需要查找到的temp是temp的下一个节点id等于传入的参数再进行删除

    //根据id删除员工
    public void delete(int id){
        EmpNode temp = head;
        //用于记录是否查找到id相同的emp
        boolean flag = true;
        while (true){
            if (temp.next == null){
                flag = false;
                break;
            }
            if (temp.next.id == id){
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.printf("您需要删除的id为%d的员工不存在",id);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

面试题

求单链表中有效节点的个数

思路分析：比较简单，使用一个计数器，遍历节点即可。

    /**
     * 返回链表的有效节点个数
     * @param head 头节点
     * @return
     */
    public static int getSize(EmpNode head){
        if (head.next == null){
            return 0;
        }
        EmpNode cur = head.next;
        int size = 0; //用于记录个数
        while (cur != null){
            size ++;
            cur = cur.next;
        }
        return size;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

查找单链表中的倒数第k个节点

思路分析：遍历两次，第一次遍历得到链表的有效节点个数，第二次遍历到倒数第k个节点的位置

    /**
     * 获取链表中倒数第k个节点
     * @param head,index
     * @return
     */
    public static EmpNode getLastIndex(EmpNode head,int index){
        if (head.next == null){
            return null;
        }
        int size = getSize(head);//获取链表的有效节点个数
        EmpNode cur = head.next;
        if (index <= 0 || size < index){
            return null;
        }
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方式二：使用双指针，这样只需要遍历一次，起点两个指针相同，当第一根指针走k步之后，第二根指针才开始同步移动

    /**
     * 获取链表倒数第k个节点，只允许循环一次
     * @param head
     * @param index
     * @return
     */
    public static EmpNode getLastIndexOne(EmpNode head,int index){
        if (head.next == null){
            return null;
        }
        //使用双指针，第一个指针先动index次，第二个指针再开始遍历
        EmpNode temp = head.next;
        EmpNode result = head.next;
        int count = 0;
        while (true){
            count ++;
            if (temp.next == null){
                if (index > count){
                    result = null;
                }
                break;
            }
            temp = temp.next;
            if (index <= count){
                result = result.next;
            }
        }
        return result;
    }
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

单链表的反转

思路分析：准备一个新的链表头，遍历链表，没遍历一个节点将数据添加到新链表的最前端

    /**
     * 反转单链表
     * @param head
     */
    public static void reverseList(EmpNode head){
        //当链表中没有数据或者链表只有一个节点时，无需反转
        if (head.next == null || head.next.next == null){
            return;
        }
        EmpNode reverseHead = new EmpNode(0, "");
        EmpNode cur = head.next;
        while (cur != null){
            EmpNode temp = cur.next;//将cur的下一个节点临时存入temp
            cur.next = reverseHead.next;//将cur的下一个节点指向临时头节点的下一个节点
            reverseHead.next = cur;//将临时头节点的下一个节点指向cur
            cur = temp;
        }
        head.next = reverseHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

逆向打印单链表

思路分析：

方式一：使用上一个知识点，先反转单链表再遍历输出，但这种情况我们不推荐使用，因为会破坏原先链表的结构。

方式二：使用栈，栈的特点是先进后出，链表的特点是在内存中无序排放的，所以可以先遍历链表，将每一个节点压入到栈中，再从栈中取出即可

    /**
     * 逆向打印单链表
     * @param head
     */
    public static void reversePrint(EmpNode head){
        if (head.next == null){
            System.out.println("链表为空");
        }
        Stack<EmpNode> stack = new Stack<>();//创建栈
        EmpNode cur = head.next;
        while (cur != null){
            //将节点压入栈
            stack.push(cur);
            cur = cur.next;
        }
        //读取数据
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

合并两个有序的单链表，合并之后链表依然有序

思路分析：创建一个新的链表，比较两个单链表头节点的下一个节点的ID，ID小的添加到新的链表中。

    /**
     * 合并两个有序链表
     * @param head1
     * @param head2
     * @return
     */
    public static SingleLinkedList merge2LinkedList(EmpNode head1,EmpNode head2){
        SingleLinkedList mergeLinkedList = new SingleLinkedList();
        EmpNode cur = mergeLinkedList.getHead().next;
        while (head1.next != null || head2.next != null){
            //其中有一个链表插入完了处理
            if (head1.next == null){
                cur.next = head2.next;
                break;
            }
            if (head2.next == null){
                cur.next = head1.next;
                break;
            }
            if (head1.next.id < head2.next.id){
                cur = head1.next;
                if (head1.next.next == null){
                    head1.next = null;
                }else {
                    head1.next = head1.next.next;
                }
            }else {
                cur = head2.next;
                if (head2.next.next == null){
                    head2.next = null;
                }else {
                    head2.next = head2.next.next;
                }
            }
            mergeLinkedList.addById(cur);
        }
        return mergeLinkedList;
    }
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

双向链表

双向链表与单向链表的区别在于：单向链表每一个节点只记录下一个节点的信息，而双向链表除了记录下一个节点信息之外，还记录前一个节点的信息。

思路分析

同样，我们来实现双向链表的增删改查功能，首先来分析一波

查询：跟单向链表一样，遍历输出即可

增加：在链表末尾添加数据，除了将末尾节点next属性指向新节点之外，还需要将新节点pre属性指向末尾节点

修改：跟单向链表类似，遍历找到该节点修改即可

删除：与单向链表不同，单向链表是借助一个临时节点，找到需要删除的前一个节点来进行操作。而双向链表则直接找到需要删除的节点，将他前一个节点的next属性指向他的后一个节点，并且将后一个节点的pre属性指向他的前一个节点。此步骤我们需要注意一下空指针的问题，当删除的节点是最后一个节点时，他不存在下一个节点

代码实现

说了这么多，直接上代码

/**
 * 双向链表
 */
public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();
        HeroNode hero1 = new HeroNode(1, "tom");
        HeroNode hero2 = new HeroNode(2, "jerry");
        HeroNode hero3 = new HeroNode(3, "mike");
        HeroNode hero4 = new HeroNode(4, "mary");
        list.add(hero1);
        list.add(hero2);
        list.add(hero3);
        list.add(hero4);

        System.out.println("修改前～～");
        list.list();
        list.delete(3);
        System.out.println("修改后～～");
        list.list();
    }
}

class DoubleLinkedList{
    //头节点
    private HeroNode head = new HeroNode();

    public HeroNode getHead() {
        return head;
    }

    //添加元素
    public void add(HeroNode heroNode){
        HeroNode temp = head;
        while (true){
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //修改元素
    public void update(HeroNode heroNode){
        if (head.next == null){
            System.out.println("链表为空");
        }
        HeroNode temp = head.next;
        boolean flag = true;
        while (true){
            if (temp == null){
                flag = false;
                break;
            }
            if (temp.id == heroNode.id){
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
        }else {
            System.out.println("链表中查无此数据");
        }
    }

    //删除元素
    public void delete(int id){
        if (head.next == null){
            return;
        }
        HeroNode temp = head.next;
        boolean flag = true;
        while (true){
            if (temp == null){
                flag = false;
                break;
            }
            if (temp.id == id){
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.pre.next = temp.next;
            if (temp.next != null){
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.println("链表中查无此数据");
        }
    }

    //链表的显示
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
        }
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

class HeroNode{
    public int id;
    public String name;
    public HeroNode next;
    public HeroNode pre;

    public HeroNode() {
    }

    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
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

环形链表

我们主要讲的是单向环形链表，与单向链表的区别就是没有头节点，并且最后一个节点的下一个节点指向第一个节点，形成一个闭环，这样的链表我们称之为单向环形链表

思路分析

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

解决约瑟夫问题最好的办法就是环形链表，首先我们要创建链表以及显示链表

需求：输入一个整数，环形链表中就添加这么多个节点

首先，创建一个first节点，当添加第一个节点时，将第一个节点的属性赋值给first节点，并且让firsr节点自成一环，也就是说first节点的下一个节点还是指向first；之后每次添加时，使用临时节点来遍历，我们把它想象成一个绳子绕成一圈打个结，first节点作结的一头，结的另外一头就是最后一个节点，那么最后一个节点的next属性要指向新的节点，新的节点的next属性要指向first节点

代码实现

public class CircinateLinkedListDemo {
    public static void main(String[] args) {
        CircinateLinkedList circinateLinkedList = new CircinateLinkedList();
        circinateLinkedList.add(10);
        circinateLinkedList.show();
    }
}

class CircinateLinkedList{
    //头节点先创建，后续插入第一个节点时更新
    private BoyNode first = new BoyNode();

    /**
     * 将节点插入到链表中
     * @param nums 插入节点的数量
     */
    public void add(int nums){
        if (nums < 1){
            System.out.println("请输入正确的值");
        }
        //创建一个辅助节点
        BoyNode cur = null;
        for (int i = 1; i <= nums; i++) {
            BoyNode boy = new BoyNode(i);
            if (i == 1){
                first = boy;
                first.setNext(first);//内循环
                cur = first;
            }else {
                cur.setNext(boy);
                boy.setNext(first);
                cur = boy;
            }
        }
    }

    /**
     * 遍历当前链表
     */
    public void show(){
        if (first.getNo() < 1){
            System.out.println("链表为空");
        }
        BoyNode cur = first;
        while (true){
            System.out.printf("这是第%d个小孩\n",cur.getNo());
            if (cur.getNext() == first){
                break;
            }
            cur = cur.getNext();
        }
    }

}

class BoyNode{
    private int no;
    private BoyNode next;

    public BoyNode() {
    }

    public BoyNode(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public BoyNode getNext() {
        return next;
    }

    public void setNext(BoyNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "BoyNode{" +
                "no=" + no +
                '}';
    }
}
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

解决约瑟夫问题

上面的案例有些血腥，我们要求一共有n个小男孩，从第k个小男孩开始报数，每次报m下，报到m的小男孩出圈，最后剩下一个幸运男孩。并且我们要显示出圈的顺序

思路分析

让first节点移动k下，成为一个新的first节点
创建一个helper节点，指向链表的末尾，也就是first节点的前一个节点
循环，每次移动m-1下，first和helper节点同时移动
移动完之后，first节点的下一个节点成为新的first节点，helper节点的next指向新的first节点

代码实现

    /**
     * 解决约瑟夫问题
     * @param start 从第几个小孩开始
     * @param step 从1开始报到step的小孩出圈
     * @param sum 一共有多少个小孩
     */
    public void getout(int start,int step,int sum){
        add(sum);
        if (start < 1 || start > sum || first == null){
            return;
        }
        for (int i = 0; i < start - 1; i++) {
            first = first.getNext();
        }
        BoyNode helper = first;
        //将helper节点设置为first的前一个节点
        while (true){
            if (helper.getNext() == first){
                break;
            }
            helper = helper.getNext();
        }
        while (true){
            if (helper == first){
                break;
            }
            for (int i = 0; i < step - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println("出圈的小孩id是：" + first.getNo());
            helper.setNext(first.getNext());
            first = first.getNext();
        }
        System.out.println("幸运儿id为：" + first.getNo());
    }
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/817366