链表是什么？学过数据结构的人都很清楚，链表就是一种最最最基本的数据结构，基本到什么程度呢？基本到数据结构课上所学的数据结构都可以用链表来实现。

正因为其基础，我们更要了解链表的基本操作。

链表的构成及基本操作

首先了解链表（单向）的构成：链表由一个个统一的节点构成，节点一般由两个变量构成：

  • 一个值，可以为各种类型
  • 一个指向下一个节点的“指针”

链表的基本操作和多数数据结构相同，即插入，删除，查找等等。均很简单，也不再赘述，主要说说插入操作：

  • 从头插入：新建的节点插入到链表头部
  • 从尾插入：新建的节点插入到链表尾部
  • 从任意位置插入：字面意思。

下面实现链表的构成及其基本操作（LeetCode 对应题目：707. 设计链表）

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
class MyLinkedList {
    private class Node{
		int val;
		Node next;
		Node(int val){
			this.val = val;
			this.next = null;
		}
	}

    private Node head,tail;
	private int size;

    /** Initialize your data structure here. */
    public MyLinkedList() {
        Node node = new Node(0);
        this.head = node;
        this.tail = node;
        this.size = 0;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if (index < 0 || index >= this.size) 
            return -1;
        Node node = head;
        for (int i = 0; i < index; i++){
            node = node.next;
        }
        return node.val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        if (this.size == 0)
            this.head.val = val;
        else {
            Node tmp = new Node(val);
            tmp.next = head;
            this.head = tmp;
        }
        this.size++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if (this.size == 0)
            this.tail.val = val;
        else {
            Node tmp = new Node(val);
            this.tail.next = tmp;
            this.tail = tmp;
        }
        this.size++;
    }
    
    /**
     * Add a node of value val before the index-th node in the linked list.
     * If index equals to the length of linked list, 
     * the node will be appended to the end of linked list.
     * If index is greater than the length, the node will not be inserted.
     */
    public void addAtIndex(int index, int val) {
        if (index > this.size) return;

        if (index == this.size) {
            addAtTail(val);
        } else if (index <= 0) {
            addAtHead(val);
        } else {
            Node node = new Node(val);        
            Node tmp = head;
            for(int i = 1; i < index; i++) {
                tmp = tmp.next;
            }
            node.next = tmp.next;
            tmp.next = node;
            this.size++;
        }
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= this.size) return;

        if (index == 0) {
            this.head = this.head.next;
        } else {
            Node node = head;
            for (int i = 1; i < index; i++) {
                node = node.next;
            }
            node.next = node.next.next;
            if (index == this.size-1) {
                tail = node;
            }
        }
        this.size--;
    }
}

链表的反转

什么是反转，简单来说，就是将 12345 变为 54321 ，这便是反转。就链表而言，反转操作一般要求原地操作，尽可能减少空间使用，并且不允许直接改变链表的值。

表面来看反转好像很简单，但是实质上真正写起来也不是那么简单。链表操作的重难点，就是要防止链表断链丢失，所以，为了实现反转操作，我们需要三个节点指针，其过程如下图所示：

链表反转1.png
链表反转1.png

反转的代码如下：

1
2
3
4
5
6
7
8
9
10
private ListNode flipList(ListNode ptr, ListNode tail) {
	ListNode newHead = null;
	while (ptr != tail) {
		ListNode next = ptr.next;
		ptr.next = newHead;
		newHead = ptr;
		ptr = next;
	}
	return ptr;
}

实质上就是将链表的箭头给翻转过来，而为了使链表不断链丢失，所以引入了三个指针。

LeetCode 相关问题：

链表排序

链表排序可以直接将数组排序的算法代入其中，选择，归并啥的，只需要注意指针的完整性即可，下面附上链表的归并排序的函数（即：148. 排序链表）：

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
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)  return head;
        
        ListNode quick, slow;
        quick = head.next;
        slow = head;
        while (quick != null && quick.next != null) {
            quick = quick.next.next;
            slow = slow.next;
        }
        
        ListNode mid = slow.next;
        slow.next = null;
        ListNode head1 = sortList(head);
        ListNode head2 = sortList(mid);
        
        ListNode newHead = new ListNode(-1);
        ListNode ptr = newHead;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                ptr.next = head1;
                head1 = head1.next;
            } else {
                ptr.next = head2;
                head2 = head2.next;
            }
            ptr = ptr.next;
        }
        
        ptr.next = head1 == null ? head2 : head1; 
        return newHead.next;
    }
}

LeetCode 其余相关问题：