leedcode 初级算法 链表

链接

删除链表中的节点

题目解析

请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。

题目解析

懒得解析了

删除链表的倒数第N个节点

题目描述

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

题目解析 方法一

为头节点head建立一个前驱结点heeaad,这样就不怕只有head一个结点的情况了。先遍历一遍链表得到链表的长度,再从heeaad遍历链表,r->next,指向的是当前应该删除的结点。记住不要让r指向当前应该删除的结点,不然含需要一个r的前驱节点。

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
class Solution
{
public:
int getLength(ListNode *head)
{
int length = 0;
while (head)
{
length++;
head = head->next;
}
return length;
}
ListNode *removeNthFromEnd(ListNode *head, int n)
{
int length = getLength(head);
if (length == 0)
return NULL;
n = length + 1 - n; //正数
ListNode *heeaad = new ListNode(0, head); //声明一个指向head结点的结点,值为零
ListNode *r = new ListNode;
r = heeaad;
for (int i = 1; i <= n - 1; i++)
{
r = r->next;
}
//得到当前要删除的为 r->next
r->next = r->next->next;
ListNode *ans = heeaad->next;
delete heeaad;
return ans;
}
};
题目解析 方法二

使用栈,向将链表中的所有数据先存起来,然后依次从前面插入。

反转链表

题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

题目解析 方法一

遍历一遍,从左到右依次设置三个指针t1 t2 t3。
每一个循环中的装填都是 t2已经设置好指向,t2需要改变指向到t1,t3指向下一轮循环需要改变的结点。

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
using namespace std;

struct ListNode
{
int val;
struct ListNode *next;
};

struct ListNode *reverseList(struct ListNode *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
ListNode *t1 = NULL, *t2 = NULL, *t3 = NULL;
t1 = head;
t2 = head->next;
t1->next = NULL;
do
{
t3 = t2->next;
t2->next = t1;
if (t3 == NULL)
{
return t2;
}
t1 = t2;
t2 = t3;
t3 = t3->next;
} while (1);
return NULL;
}
题目解析 方法二

递归

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
using namespace std;

struct ListNode
{
int val;
struct ListNode *next;
};

struct ListNode *reverseList(struct ListNode *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
struct ListNode *res = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return res;
}

合并有序链表

题目描述

合并两个递增链表

题目解析 方法一

迭代,先设立一个伪头节点,比较l1 l2的大小,将游标指向小的,并后移对应链表l1或l2,直到一个为空

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
#include <malloc.h>
#include <random>
#include <time.h>
using namespace std;

struct ListNode
{
int val;
struct ListNode *next;
};

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
{
struct ListNode *res = (struct ListNode *)malloc(sizeof(struct ListNode));
res->next = NULL;
struct ListNode *t = res;
while (1)
{
if (l1 == NULL)
{
t->next = l2;
return res->next;
}
if (l2 == NULL)
{
t->next = l1;
return res->next;
}
if (l1->val <= l2->val)
{
t->next = l1;
l1 = l1->next;
t = t->next;
}
else
{
t->next = l2;
l2 = l2->next;
t = t->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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
#include <malloc.h>
#include <random>
#include <time.h>
using namespace std;

struct ListNode
{
int val;
struct ListNode *next;
};

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2)
{
if (l1 == NULL)
{
return l2;
}
if (l2 == NULL)
{
return l1;
}
if (l1->val <= l2->val)
{
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else
{
l2->next = mergeTwoLists(l2->next, l1);
return l2;
}
}

回文链表

题目描述

判断一个链表是否是回文链表

题目解析 方法一

将链表从中间分为两部分,将其中一部分进行反转,顺序比较是否相等。

这个解法和力扣官方解法的快慢指针相同。

在并发环境中这个解法需要进行链表访问的锁定,因为在访问中会进行更改链表。

在程序的最后还需要将链表复原。

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <utility>
#include <map>
#include <stack>
#include <malloc.h>
#include <random>
#include <time.h>
using namespace std;

struct ListNode
{
int val;
struct ListNode *next;
};

struct ListNode *reverseList(struct ListNode *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
struct ListNode *res = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return res;
}

bool isPalindrome(struct ListNode *head)
{
int count = 0;
struct ListNode *h = head;
while (h)
{
count++;
h = h->next;
}
count /= 2;
struct ListNode *l1 = head;
struct ListNode *l2 = head;
while (count > 0)
{
count--;
l2 = l2->next;
}
l2 = reverseList(l2);
while (l1 && l2)
{
if (l1->val != l2->val)
{
return false;
}
l1 = l1->next;
l2 = l2->next;
}
return true;
}
题目解析 方法二

复制到数组里面,这个方法太幼稚了。略。

题目解析 方法三

递归,使用后序遍历的递归。由于递归天然具有从后向前的特性,所以用来从后向前遍历是再好不过的。在函数外设置一个变量用来指示从前向后遍历进行并比较的结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ListNode *now = NULL;

bool check(struct ListNode *head)
{
if (head)
{
if (!check(head->next))
return false;
if (head->val != now->val)
{
return false;
}
now = now->next;
}
return true;
}

bool isPalindrome(struct ListNode *head)
{
now = head;
return check(head);
}

环形链表

题目描述

判断一个链表是否有环,即遍历永远不会结束。

题目解析 方法一

这是一个投机的方法。根据是系统分配内存是从小开始分配。不可以在真实环境中使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool hasCycle(struct ListNode *head)
{
if (head == NULL || head->next == NULL)
{
return false;
}
while (head->next)
{
if (head->next <= head)
return true;
head = head->next;
}
return false;
}
题目解析 方法二

使用哈希表记录每一次遍历到的结点地址。遍历时判断是否已经遍历过。

1
2
3
4
5
6
7
8
9
10
11
12
bool hasCycle(struct ListNode *head)
{
unordered_set<struct ListNode *> set;
while(head)
{
if(set.count(head))
return true;
set.insert(head);
head=head->next;
}
return false;
}
题目解析 方法三

快慢指针

使用两个指针 兔子和乌龟 兔子一次走两步,乌龟一次走一步,直到结尾。若相遇说明有环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool hasCycle(struct ListNode *head)
{
if (head == NULL || head->next == NULL)
return false;
struct ListNode *tu, *gui;
gui = head;
tu = head->next;
while (tu && gui)
{
if (tu == gui)
return true;
gui = gui->next;
tu = tu->next;
if (tu == NULL)
return false;
else
tu = tu->next;
}
return false;
}