目录

单向链表

介绍

链表是有序的列表(List),物理存储结构如下所示

https://gitee.com/lienhui68/picStore/raw/master/null/20200616144600.png

逻辑结构如下

https://gitee.com/lienhui68/picStore/raw/master/null/20200616144630.png

链表的特点主要有

  • 以节点方式存储,链式存储
  • 每个节点包含data、next指针,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
package com.eh.ftd.dsa.ds.impl;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/16 14:24
 */
public class SingleLinkedList<E> {

    private Node head = new Node();

    /**
     * 首先定义一个节点用来包装数据
     *
     * @param <E>
     */
    class Node<E> {
        private E e;
        private Node next;

        public Node() {
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    '}';
        }
    }

    /**
     * 增加一个元素
     *
     * @param e
     * @return
     */
    public boolean add(E e) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(e, null);
        return true;
    }

    /**
     * 用来演示
     */
    public void display() {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
            System.out.println(temp.e);
        }
    }

    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.display();
    }
}

几道单链表相关的面试题

求链表的倒数第k个元素

  1. 先遍历获取链表元素个数n
  2. 遍历获取第(n-k)个元素

在原有的链表基础上逆序

传送门: 单向链表逆序

合并两个有序列表

比较简单,直接给出代码

 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
public static SingleLinkedList mergeDemo(SingleLinkedList list1, SingleLinkedList list2) {
        SingleLinkedList list = new SingleLinkedList();
        Node cur1 = list1.head.next;
        Node cur2 = list2.head.next;
        while (cur1 != null || cur2 != null) {
            if (cur1 == null) {
                list.add(cur2);
                cur2 = cur2.next;
                continue;
            }
            if (cur2 == null) {
                list.add(cur1);
                cur1 = cur1.next;
                continue;
            }
            int val1 = (int) cur1.e;
            int val2 = (int) cur2.e;

            if (val1 < val2) {
                list.add(cur1);
                cur1 = cur1.next;
            } else if (val1 == val2) {
                list.add(cur1);
                list.add(cur2);
                cur1 = cur1.next;
                cur2 = cur2.next;
            } else {
                list.add(cur2);
                cur2 = cur2.next;
            }
        }

        return list;
    }

public static void main(String[] args) {
        SingleLinkedList list1 = new SingleLinkedList();
        list1.add(1);
        list1.add(3);
        list1.add(5);
        list1.add(7);
        SingleLinkedList list2 = new SingleLinkedList();
        list2.add(2);
        list2.add(4);
        list2.add(6);
        list2.add(8);
        list2.add(9);
        list2.add(10);
        list2.add(11);
        System.out.println("========合并后的结果========");
        SingleLinkedList list = mergeDemo(list1, list2);
        list.display();
    }

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200616162703.png