数据结构---单向链表，双向链表，单向环形链表

链表介绍

1. 链表是以节点的方式来存储,是链式存储
2. 每个节点包含 data 域， next 域:指向下一个节点.
3. 如图:发现链表的各个节点不一定是连续存储.
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

修改节点功能
思路(1) 先找到该节点，通过遍历，(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname

HeroNode**

package com.linkedlist;

class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点
    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name; this.nickname = nickname;
    }
    //为了显示方法，我们重新 toString @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

定义 SingleLinkedList 管理我们的英雄

package com.linkedlist;

//定义 SingleLinkedList 管理我们的英雄
class SingleLinkedList {
    //先初始化一个头节点, 头节点不要动, 不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    //添加节点到单向链表 //思路，当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的 next 指向 新的节点
    public void add(HeroNode heroNode) {

        //因为 head 节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {//

                break;
            }
            //如果没有找到最后, 将将 temp 后移
            temp = temp.next;
        }

        //当退出 while 循环时，temp 就指向了链表的最后 //将最后这个节点的 next 指向 新的节点
        temp.next = heroNode;
    }

    //第二种方式在添加英雄时，根据排名将英雄插入到指定位置 //(如果有这个排名，则添加失败，并给出提示)

    public void addByOrder(HeroNode heroNode) {
        //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
        // 因为单链表，因为我们找的 temp 是位于 添加位置的前一个节点，否则插入不了

        HeroNode temp = head;

        boolean flag = false; // flag 标志添加的编号是否存在，默认为 false
        while(true) {
            if(temp.next == null) {//说明 temp 已经在链表的最后
                break; //
            }

            if(temp.next.no > heroNode.no) { //位置找到，就在 temp 的后面插入
                 break;
            } else if (temp.next.no == heroNode.no) {
                //说明希望添加的 heroNode 的编号已然存在
                flag = true; //说明编号存在
                break;
            }

            temp = temp.next; //后移，遍历当前链表
        }
        //判断 flag 的值
        if(flag) { //不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
        } else {
            //插入到链表中, temp 的后面
            heroNode.next = temp.next;
            temp.next = heroNode;

        }
    }


    //修改节点的信息, 根据 no 编号来修改，即 no 编号不能改. //说明
    //1. 根据 newHeroNode 的 no 来修改即可

    public void update(HeroNode newHeroNode) {
        //判断是否空
        if(head.next == null) {
            System.out.println("链表为空~");
            return;
        }

        //找到需要修改的节点, 根据 no 编号 //定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false; //表示是否找到该节点
        while(true) {
            if (temp == null) {
                break; //已经遍历完链表
            }
            if(temp.no == newHeroNode.no) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据 flag 判断是否找到要修改的节点
        if(flag) {
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
        } else { //没有找到
                System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
        }
    }


    //删除节点
    //思路
    //1. head 不能动，因此我们需要一个 temp 辅助节点找到待删除节点的前一个节点 //2. 说明我们在比较时，是 temp.next.no 和 需要删除的节点的 no 比较


    public void del(int no) {

        HeroNode temp = head;

        boolean flag = false; // 标志是否找到待删除节点的
        while (true) {
            if (temp.next == null) { //已经到链表的最后
                break;
            }

            if (temp.next.no == no) {
                //找到的待删除节点的前一个节点temp
                flag = true;
                break;
            }

            temp = temp.next; //temp 后移，遍历 }
            //判断 flag

            if (flag) { //找到
                //可以删除
                temp.next = temp.next.next;
            } else {
                System.out.printf("要删除的 %d 节点不存在\n", no);
            }
        }
    }

    //显示链表[遍历]

    public void list() {
        //判断链表是否为空
        if(head.next == null) {

            System.out.println("链表为空");
            return;
        }
        //因为头节点，不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while(true) {
            //判断是否到链表最后
            if(temp == null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp); //将 temp 后移， 一定小心
            temp = temp.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
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

SingleLinkedListDemo

package com.linkedlist;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //进行测试
        // 先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建要给链表

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //加入
        // singleLinkedList.add(hero1);
        // singleLinkedList.add(hero4);
        // singleLinkedList.add(hero2);
        // singleLinkedList.add(hero3);
        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        //显示一把
        singleLinkedList.list();
        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);
        System.out.println("修改后的链表情况~~");
        singleLinkedList.list();
        //删除一个节点
        singleLinkedList.del(1);
        singleLinkedList.del(4);
        System.out.println("删除后的链表情况~~");
        singleLinkedList.list();
    }
}
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

单链表面试题

1. 求单链表中有效节点的个数（关键代码）

//方法:获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点) /**
*
* @param head 链表的头节点
* @return 返回的就是有效节点的个数 */
public static int getLength(HeroNode head) { 
    if(head.next == null) { //空链表
        
        return 0; 
    }
    int length = 0;

        //定义一个辅助的变量, 这里我们没有统计头节点 
    HeroNode cur = head.next;
    while(cur != null) {
        length++;
        cur = cur.next; //遍历 
    }
    return length; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

查找单链表中的倒数第k个结点【新浪面试题】

//查找单链表中的倒数第 k 个结点 【新浪面试题】 //思路
//1. 编写一个方法，接收 head 节点，同时接收一个 index
//2. index 表示是倒数第 index 个节点
//3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
//4. 得到 size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到 //5. 如果找到了，则返回该节点，否则返回 nulll
public static HeroNode findLastIndexNode(HeroNode head, int index) {
//判断如果链表为空，返回 null 
    if(head.next == null) {
        return null;//没有找到 
    }
    //第一个遍历得到链表的长度(节点个数)
    int size = getLength(head);
    //第二次遍历 size-index 位置，就是我们倒数的第 K 个节点 //先做一个 index 的校验
    if(index <=0 || index > size) {
        return null; 
    }
    //定义给辅助变量， for 循环定位到倒数的 index HeroNode cur = head.next; //3 // 3 - 1 = 2
    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
20
21
22

单链表的反转【腾讯面试题，有点难度】

//将单链表反转
public static void reversetList(HeroNode head) {
//如果当前链表为空，或者只有一个节点，无需反转，直接返回 
    if(head.next == null || head.next.next == null) {
        return ; 
    }

    //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    HeroNode cur = head.next;
    HeroNode next = null;// 指向当前节点[cur]的下一个节点
    HeroNode reverseHead = new HeroNode(0, "", ""); //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端 //动脑筋
    while(cur != null) {
        next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
        cur.next = reverseHead.next;//将 cur 的下一个节点指向新的链表的最前端 
        reverseHead.next = cur; //将 cur 连接到新的链表上
        cur = next;//让 cur 后移
    }
    //将 head.next 指向 reverseHead.next , 实现单链表的反转 
    head.next = reverseHead.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

从尾到头打印单链表【百度，要求方式1:反向遍历。方式2:Stack栈】

package com.atguigu.linkedlist; import java.util.Stack;
//演示栈 Stack 的基本使用 
public class TestStack {
    public static void main(String[] args) { 
        Stack<String> stack = new Stack(); // 入栈
        stack.add("jack"); stack.add("tom"); 
        stack.add("smith");
        // 出栈
        // smith, tom , jack 
        while (stack.size() > 0) {
            System.out.println(stack.pop());//pop 就是将栈顶的数据取出 
        }  
    }     
}
*********************************************************



//方式 2: //可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效
果
public static void reversePrint(HeroNode head) { 
    if(head.next == null) {
   		 return;//空链表，不能打印 
    }
    //创建要给一个栈，将各个节点压入栈 
    Stack<HeroNode> stack = new Stack<HeroNode>(); 
    HeroNode cur = head.next; //将链表的所有节点压入栈
    while(cur != null) {
        stack.push(cur);
        cur = cur.next; //cur 后移，这样就可以压入下一个节点 
    }
    //将栈中的节点进行打印,pop 出栈 
    while (stack.size() > 0) {
        System.out.println(stack.pop()); //stack 的特点是先进后出 
    }
}
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

双向链表

1. 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

2. 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除

添加节点：

• // 当退出 while 循环时，temp 就指向了链表的最后
• // 形成一个双向链表 temp.next = heroNode; heroNode.pre = temp;

修改节点：

// 根据 flag 判断是否找到要修改的节点 
if (flag) {
    temp.name = newHeroNode.name;
    temp.nickname = newHeroNode.nickname; 
} else { // 没有找到
    System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no); 
}
1
2
3
4
5
6
7

删掉节点：

// 判断 flag
if (flag) { // 找到
    // 可以删除
    // temp.next = temp.next.next;[单向链表]
    temp.pre.next = temp.next;
    // 这里我们的代码有问题?
    // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针 
    if (temp.next != null) {
        temp.next.pre = temp.pre; 
    }
} else {
    System.out.printf("要删除的 %d 节点不存在\n", no);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

单向环形链表

约瑟夫环问题（Josephu）问题

Josephu 问题为:设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k(1<=k<=n)的人从 1 开始报数，数到m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此
产生一个出队编号的序列。

添加节点

// 使用 for 来创建我们的环形链表
for (int i = 1; i <= nums; i++) {
    // 根据编号，创建小孩节点 
    Boy boy = new Boy(i);
    // 如果是第一个小孩
    if (i == 1) {
        first = boy;
        first.setNext(first); // 构成环
        curBoy = first; // 让 curBoy 指向第一个小孩
    } else { 
        curBoy.setNext(boy);// 
        boy.setNext(first);// 
        curBoy = boy;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15