Linked Lists

Data Structure, Linked Lists, leetcode

链表

单链表

创建、插入和删除
在单链表中插入元素
在单链表中删除元素

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
#include <iostream>
class ListNode 
{
public:
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}

	void append_to_tail(int v);
};
void ListNode::append_to_tail( int v )
{
	ListNode* end = new ListNode(v);
	ListNode* node(this);
	if (!node) return;
	while (node->next)
	{
		node = node->next;
	}
	node->next = end;
}
ListNode* insert_node_to_pos(ListNode* head, int pos, int val)
{
	int def_pos(pos-1);
	if (!head) return new ListNode(val);	// empty head
	if (!def_pos)	// insert to head
	{
		ListNode* newhead = new ListNode(val);
		newhead->next = head;
		return newhead;
	}
	ListNode* node(head);
	while (node->next)
	{
		if (def_pos == 1)
		{
			ListNode* newnode = new ListNode(val);
			newnode->next = node->next;
			node->next = newnode;
			return head;	// head didn't change
		}
		node = node->next;
		--def_pos;
	}
	if (def_pos != 1) head->append_to_tail(val);
	return head;
}
ListNode* delete_node(ListNode* head, int val)
{
	if (!head) return NULL;
	if (head->val == val)
	{
		return head->next;	// moved head
	}
	ListNode* node(head);
	while (node->next)
	{
		if (node->next->val == val)
		{
			node->next = node->next->next;
			return head;	// head didn't change
		}
		node = node->next;
	}
	return head;
}
void print_list(ListNode* head)
{
	std::cout << "List: " << std::endl;
	while (head)
	{
		std::cout << head->val << " ";
		head = head->next;
	}
	std::cout << std::endl;
}
int main()
{
	// test NULL
	std::cout << "-----Test NULL-----" << std::endl;
	ListNode* head = NULL;
	print_list(head);
	head = delete_node(head, 0);
	print_list(head);
	head = insert_node_to_pos(head, 1, 1);
	print_list(head);
	// test head
	std::cout << "-----Test head-----" << std::endl;
	print_list(head);
	head = insert_node_to_pos(head, 1, 2);
	print_list(head);
	head = delete_node(head, 2);
	print_list(head);
	// test not exist
	std::cout << "-----Test not exist-----" << std::endl;
	print_list(head);
	head = insert_node_to_pos(head, 10, 3);
	print_list(head);
	head = delete_node(head, 5);
	print_list(head);
	// test normal
	std::cout << "-----Test normal-----" << std::endl;
	head->append_to_tail(4);
	head->append_to_tail(5);
	head->append_to_tail(6);
	head->append_to_tail(7);
	print_list(head);
	head = insert_node_to_pos(head, 3, 50);
	print_list(head);
	head = delete_node(head, 50);
	print_list(head);
	system("Pause");
};

双链表

创建、插入和删除

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
#include <iostream>
class ListNode 
{
public:
	int val;
	ListNode *prev;
	ListNode *next;
	ListNode(int x) : val(x), prev(NULL), next(NULL) {}

	void append_to_tail(int v);
};
void ListNode::append_to_tail( int v )
{
	ListNode* end = new ListNode(v);
	ListNode* node(this);
	if (!node) return;
	while (node->next)
	{
		node = node->next;
	}
	end->prev = node;
	node->next = end;
}
ListNode* insert_node_to_pos(ListNode* head, int pos, int val)
{
	int def_pos(pos-1);
	if (!head) return new ListNode(val);	// empty head
	if (!def_pos)	// insert to head
	{
		ListNode* newhead = new ListNode(val);
		newhead->next = head;
		head->prev = newhead;
		return newhead;
	}
	ListNode* node(head);
	while (node->next)
	{
		if (def_pos == 1)
		{
			ListNode* newnode = new ListNode(val);
			newnode->next = node->next;
			node->next = newnode;
			newnode->prev = node;
			newnode->next->prev = newnode;
			return head;	// head didn't change
		}
		node = node->next;
		--def_pos;
	}
	if (def_pos != 1) head->append_to_tail(val);
	return head;
}
ListNode* delete_node(ListNode* head, int val)
{
	if (!head) return NULL;
	if (head->val == val)
	{
		head->next->prev = NULL;
		return head->next;	// moved head
	}
	ListNode* node(head);
	while (node->next)
	{
		if (node->next->val == val)
		{
			node->next = node->next->next;
			node->next->prev = node;
			return head;	// head didn't change
		}
		node = node->next;
	}
	return head;
}
void print_list(ListNode* head)
{
	std::cout << "List: " << std::endl;
	ListNode* end(NULL);
	while (head)
	{
		if (!head->next) {end = head;}
		std::cout << head->val << " ";
		head = head->next;
	}
	std::cout << std::endl;
	while (end)
	{
		std::cout << end->val << " ";
		end = end->prev;
	}
	std::cout << std::endl;
}
int main()
{
	// test NULL
	std::cout << "-----Test NULL-----" << std::endl;
	ListNode* head = NULL;
	print_list(head);
	head = delete_node(head, 0);
	print_list(head);
	head = insert_node_to_pos(head, 1, 1);
	print_list(head);
	// test head
	std::cout << "-----Test head-----" << std::endl;
	print_list(head);
	head = insert_node_to_pos(head, 1, 2);
	print_list(head);
	head = delete_node(head, 2);
	print_list(head);
	// test not exist
	std::cout << "-----Test not exist-----" << std::endl;
	print_list(head);
	head = insert_node_to_pos(head, 10, 3);
	print_list(head);
	head = delete_node(head, 5);
	print_list(head);
	// test normal
	std::cout << "-----Test normal-----" << std::endl;
	head->append_to_tail(4);
	head->append_to_tail(5);
	head->append_to_tail(6);
	head->append_to_tail(7);
	print_list(head);
	head = insert_node_to_pos(head, 3, 50);
	print_list(head);
	head = delete_node(head, 50);
	print_list(head);
	system("Pause");
};

快慢指针技巧(The “Runner” Technique)

The “runner” (or second pointer) technique means that you iterate through the linked list with two pointers simultaneously, with one ahead of the other. The “fast” node might be ahead by a fixed amount, or it might be hopping multiple nodes for each one node that the “slow” node iterates through.

用递归解决

链表问题往往用递归可以解决。不过递归需要至少O(n)的额外空间，n是递归的数目。所有的递归算法都可以用复杂一些的迭代实现。

STL中的list

STL中的list是双向链表。详细内容见这里。

相关leetcode问题(单链表)

链表问题常常在首部添加一个做记录的dummy节点，要时刻警惕是否为NULL，看清题目是单链表还是双链表还是什么自定义的特殊链表，如果涉及到给定数字注意该数字是否大于链表长度，注意考虑特殊元素是队首、队尾、队列只有一个元素等情况，过程经常是渐进式地满足一个规律迭代前进，迭代过程中要时刻注意指针的指向是否已变化，比较细碎的地方要多用实例测试，一个链表可以分为多个子链表处理，多个子链表也可以合并到一个链表中，快慢指针技法。
Add Two Numbers | 相似：[Arrays] Plus One
Reverse Linked List II
Partition List
Remove Duplicates from Sorted List
Remove Duplicates from Sorted List II
Rotate List
Remove Nth Node From End of List
Swap Nodes in Pairs
Reverse Nodes in k-Group
Copy List with Random Pointer
Linked List Cycle
Linked List Cycle II
Reorder List
LRU Cache
Intersection of Two Linked Lists
Remove Linked List Elements
Reverse Linked List
Delete Node in a Linked List
Palindrome Linked List
Odd Even Linked List

[1] Cracking the Coding Interview
[2] leetcode
[3] 数据结构（C语言版）