[算法]模式识别-List

Author Avatar
与狼同行 11月 25, 2016

List

1
2
3
4
5
6
class ListNode {
public:
ListNode(int a):value(a){}
ListNode *next;
int value;
};

链表分为单向链表和双向链表,与数组类似,搜索链表需要O(n)的时间复杂度,但是链表不能通过常数时间来读取第k个元素。链表的优势在于以较高效率任意插入或者删除元素。

技巧

1. 哑节点Dummy Node:操作头结点时,不妨创建一个亚节点,这样操作头结点和其他节点一样没有什么区别。

这里有个试题:把小于x的元素放到左边,大于x的元素放到右边,对一个链表重新排序

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
ListNode *reorderList(ListNode *head,int x){
ListNode *newHead = NULL;
ListNode *aDummy = new ListNode(0);
ListNode *aCurr = aDummy;
ListNode *bDummy = new ListNode(0);
ListNode *bCurr = bDummy;
while (head) {
ListNode *next = head->next;
head->next = NULL;
if (head->value < x) {
aCurr->next = head;
aCurr = head;
}else{
bCurr->next = head;
bCurr = head;
}
head = next;
}
aCurr->next = bDummy->next;
newHead = aDummy->next;
delete aDummy;
delete bDummy;
return newHead;
}

2. RunnerAndChaser:对于寻找链表特定位置,不妨用两个指针变量,以不同速度来遍历该链表,已找到目标位置
题目:给定一个链表,编写一个函数返回该链表的中间节点

1
2
3
4
5
6
7
8
9
10
11
ListNode *midpoint(ListNode *head){
ListNode *chaser = head, *runner = head;
if (head == NULL) {
return NULL;
}
while (runner->next && runner->next->next) {
chaser = chaser->next;
runner = runner->next->next;
}
return chaser;
}

题目:找到一个单链表中,距离最后一个元素为k的元素。例如,如果给定一个1,2,3,4如果k为2,那么函数应该返回2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode *findkthtolast(ListNode *head,int k){
ListNode *chaser = head, *runner = head;
if (head == NULL || k<0) {
return NULL;
}
for (int i=0; i<k; i++) {
runner = runner->next;
}
if (runner == NULL) {
return NULL;
}
while (runner->next != NULL) {
chaser = chaser->next;
runner = runner->next;
}
return chaser;
}

3. 遍历链表的时候,注意每次循环内只处理一个或者一对节点,否则很容易出现重复处理的问题

1
2
3
4
5
6
7
8
9
10
11
12
ListNode* reverseLinkedList(ListNode* head){
ListNode *prev = NULL;
ListNode *next = NULL;
while (head) {
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}

4.交换节点技巧:如果要交换两个节点的位置,先交换两个前驱节点的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
ListNode *swapPairs(ListNode *head){
if (head==NULL) {
return NULL;
}
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *prev = dummy;
ListNode *node1 = head,*node2 = head;
ListNode *newHead = NULL;
while (node1 && node1->next) {
node2 = node1->next;
ListNode *tmp1 = prev->next;
prev->next = node1->next;
node1->next = tmp1;
ListNode *tmp2 = node1->next;
node1->next = node2->next;
node2->next = tmp2;
prev = node1;
node1 = prev->next;
}
newHead = dummy->next;
delete dummy;
return newHead;
}

6. 同时操作两个链表:遇到同时处理两个链表的问题,循环的条件一般可以用while(list1&&list2),当循环跳出后,在处理剩下非空的链表。这相当于边界情况特殊处理,常规情况常规处理。
给定两个有序的链表,编写一个函数来合并这两个链表,并且返回一个新的有序链表

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
ListNode* mergeTwoLists(ListNode *l1,ListNode *l2){
ListNode *dummy = new ListNode(0);
ListNode *curr = dummy;
ListNode *newHeader = NULL;
while (l1 && l2) {
if (l1->value <= l2->value) {
curr->next = l1;
l1 = l1->next;
}else{
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
if (l1) {
curr->next = l1;
}else{
curr->next = l2;
}
newHeader = dummy->next;
delete dummy;
return newHeader;
}