链表/链表基础题

学习笔记

单链表节点定义

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 单链表节点定义
 */
public class Node<V> {
    public V value;
    public Node next;

    public Node(V data) {
        value = data;
        next = null;
    }
}

双向链表节点定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 双向链表结构
 * @param <V>
 */
public class DoubleNode<V> {
    public V value;
    public DoubleNode<V> last;
    public DoubleNode<V> next;

    public DoubleNode(V v) {
        value = v;
        last = null;
        next = null;
    }
}

单链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 原始单链表：a → b → c → d → null

 设计一个函数，必须有返回值（链表头部）： node=f(head) , 反转后node返回是节点d。

 目标输出单链表结构：null ← a ← b ← c ← d
 */
public class Linkedlist01_reverse_singlelist {
    public static Node reverseLinkedList(Node head) {
        //准备两个变量
        Node pre = null; // 新链表头new
        Node next = null; //旧链表头old
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

单链表实现队列

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
/**
 * 
 */
public class Linkedlist02_singlelist_implement_queue {
    /**
     *  队列结构
     * @param <V>
     */
    public static class MyQueue<V> {
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public MyQueue() {
            head = null;
            tail = null;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        /**
         * 数据压入队列
         * @param value
         */
        public void offer(V value) {
            //根据传进来的值创建一个节点
            Node<V> cur = new Node<V>(value);
            if (tail == null) {
                //初始化头部和尾部
                head = cur;
                tail = cur;
            } else {
                //从尾部追加节点
                tail.next = cur;
                tail = cur;
            }
            size++;
        }
        /**
         * 数据从队列弹出
         * @return
         */
        // C/C++的同学需要做节点析构的工作
        public V poll() {
            V ans = null;
            if (head != null) {
                ans = head.value;
                head = head.next;
                size--;
            }
            //为什么要释放tail，因为需要与head保持一致，不然tail指向的元素不会被释放
            if (head == null) {
                tail = null;
            }
            return ans;
        }

        // C/C++的同学需要做节点析构的工作
        public V peek() {
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }

    }
}

单链表实现栈

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
public class Linkedlist03_singlelist_implement_stack {
    /**
     * 栈结构
     * @param <V>
     */
    public static class MyStack<V> {
        private Node<V> head; //一个变量实现
        private int size;

        public MyStack() {
            head = null;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        /**
         * 加入数据
         * @param value
         */
        public void push(V value) {
            Node<V> cur = new Node<>(value);//新建一个节点
            if (head == null) {
                //头部
                head = cur;
            } else {
                cur.next = head;
                head = cur;
            }
            size++;
        }

        /**
         * 弹出数据
         * @return
         */
        public V pop() {
            V ans = null;
            if (head != null) {
                ans = head.value;
                head = head.next;
                size--;
            }
            return ans;
        }

        public V peek() {
            return head != null ? head.value : null;
        }

    }
}

双向链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Linkedlist04_reverse_double_linkedlist {
    /**
     * 
     * @param head
     * @return
     */
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null; // 新链表 new
        DoubleNode next = null; //旧链表 old
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }
}

双向链表实现双端队列

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
/**
 * 双链表实现双端队列
 */
public class Linkedlist05_doublelinkedlist_implement_doublequeue {
    /**
     * 双端队列
     * @param <V>
     */
    public static class MyDeque<V> {
        private DoubleNode<V> head;
        private DoubleNode<V> tail;
        private int size;

        public MyDeque() {
            head = null;
            tail = null;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        /**
         * 头部加
         * @param value
         */
        public void pushHead(V value) {
            DoubleNode<V> cur = new DoubleNode<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size++;
        }

        /**
         * 尾部加
         * @param value
         */
        public void pushTail(V value) {
            DoubleNode<V> cur = new DoubleNode<>(value);
            if (head == null) {
                //第一个节点
                head = cur;
                tail = cur;
            } else {
                //不是第一个节点
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
            size++;
        }

        /**
         * 头部弹出
         * @return ans
         */
        public V pollHead() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            return ans;
        }

        /**
         * 尾部弹出
         * @return
         */
        public V pollTail() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
            }
            return ans;
        }

        /**
         * 头部获取，不弹出
         */
        public V peekHead() {
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }

        /**
         * 尾部获取，不弹出
         * @return
         */
        public V peekTail() {
            V ans = null;
            if (tail != null) {
                ans = tail.value;
            }
            return ans;
        }

    }
}