【数据结构和算法】001 单链表 LinkedList
- 2020 年 3 月 29 日
- 筆記
一、单链表（LinkedList）介绍和内存布局
链表是有序的列表，它在内存中的实际存储结构如下：
看上去虽然无序，但他是靠灭个链表节点元素的地址和next域来分清首尾相连的顺序，如下图所示，由头指针指向第一个元素，进而第二个、三个…
链表的逻辑结构：
二、单链表创建、遍历实现以及单链表节点增、删、改、查操作
1、创建、新增、遍历显示
模型如下：1）head节点 2）中间节点 3）尾结点
每个节点的next域指向下一个节点的对象地址，尾结点为空
创建
新建所需实体类：
package ...; /** * @Author: ldk * @Date: 2020/3/29 21:18 * @Describe: */ public 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 + ''' + '}'; } }
创建 SingleLinkedList 类，编写添加和遍历的方法：
创建main方法测试：
package ...; /** * @Author: ldk * @Date: 2020/3/29 21:25 * @Describe: */ public class LinkedListTest { public static void main(String[] args) { HeroNode h1 = new HeroNode(1, "张三", "小三"); HeroNode h2 = new HeroNode(2, "李四", "小四"); HeroNode h3 = new HeroNode(3, "王五", "小五"); HeroNode h4 = new HeroNode(4, "赵六", "小六"); SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.add(h1); singleLinkedList.add(h2); singleLinkedList.add(h3); singleLinkedList.add(h4); singleLinkedList.detail(); } static class SingleLinkedList { //创建头结点 private HeroNode head = new HeroNode(0, "", ""); //节点添加方法 public void add(HeroNode heroNode) { //拿到头结点 HeroNode temp = head; //找到最后一个节点，把next域指向要添加的节点 while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = heroNode; } //显示链表【遍历】 public void detail() { if (head.next == null) { System.out.println("链表为空！"); return; } //获取一个临时指针 HeroNode temp = head.next; while (true) { if (temp.next == null){ System.out.println(temp.toString()); System.out.println("就这么多了~~"); break; } System.out.println(temp.toString()); temp = temp.next; } } } }
运行结果：
2、按顺序插入节点
上面的测试是从1,2,3,4依次插入，那么，链表本身是有序的，我们能不能按照no字段乱序插入实现自动递增排序，且从重复元素不再重复插入，
意思就是，插入顺序改成1432，但链表内部结构依然是1234
代码只需稍微对add（）方法修改一下：
//按照字段no 升序插入 public void add2(HeroNode heroNode) { //获取指针 HeroNode temp = head; while (true) { if (temp.next == null) { break; } else if (temp.next.no == heroNode.no) { System.out.println("该节点已经存在~"); return; } else if (temp.next.no > heroNode.no) { break; } temp = temp.next; } heroNode.next = temp.next; temp.next = heroNode; }
这样的插入顺序：
查看有序的打印结果，依然是1234的顺序，而且重复的元素不再插入：
其余增删改查查有时间可以做自己思考一下。这里不再赘述。
三、单链表新浪、腾讯、百度面试题
解答：
1）思路：从头结点的下一个开始，一直遍历，每遍历一个即+1，直到.next为空，此所得即为链表长度
2）依然是遍历，从第一个一直遍历到第length-k的下一个即为k
代码（后补）：
3）有点难度，但也是很清晰的。
分为母链和子链，母链双指针，子链单指针
母链拆一个节点拼接到子链头部后第一个，以此类推，得到的全新子链即为反转链：
代码（后补）：
4）同4，反转后，打印即可。
5）以其中一个链表为母链，另一个为子链，遍历子链，挨个插入母联即可。
2020-03-29 21:02:13
