数据结构之链表练习题

这些练习都是力扣中的真题,挺容易对链表有个更进一步了解的

1、删除链表中等于给定值 val 的所有节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void SListRemoveAll(SList *s, SLDataType v){
if (s->first == NULL){
return;
}
if(s->first->value == v){
Node *next = s->first;
s->first = s->first->next;
free(s->first);
}
else{
Node *c = s->first;
while(c->next != NULL){
if(c->next->value == v){
Node *next = c->next;
c->next = c->next->next;
free(c->next);
}
else{
c = c->next;
}
}
}
}

2、 反转一个单链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SListReverse(SList *head){
Node *result = NULL;
Node *c = head;

while(c != NULL){
Node *next = c->next;

c->next = result;
result = c;

c = next;
}
return result;
}

3、给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个 中间结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node* middleNode(SList *head){
if(head == NULL){
return NULL;
}//利用快慢指针的思想
Node *fast = head;
Node *slow = head;
while(1){
fast = fast->next;
if(fast == NULL){
break;
}
slow = slow->next;
fast = fast->next;
if(fast == NULL){
break;
}
}
return slow;
}

4、输入一个链表,输出该链表中倒数第k个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Node *FindKthToTail(Node *head, unsigned int k){
Node *front = head;
Node *back = head;
//让前面的先走k步
int i;
for(i = 0;i < k && front != NULL;i++){
front = front->next;
}
if(i < k){
return NULL;
}
while(front != NULL){
front = front->next;
back = back->next;
}
return back;
}

5、 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成 的。新链表也是有序的。

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
Node* mergeTwoList(SList *c1, SList *c2){

struct SList *c1 = l1;
struct SList *c2 = l2;
struct SList *result = NULL;
struct SList *last = NULL;

if(l1 == NULL){
return l2;
}
if(l2 == NULL){
return l1;
}
while(l1 != NULL && l2 != NULL){
if(l1->value <= l2->value){
if(result == NULL){
result = last = l1;
}
else{
last->next = last;
last = l1;
}
l1 = l1->next;
}
else{
if(result == NULL){
result = last = l2;
}
else{
last->next = last;
last = l2;
}
l2 = l2->next;
}
}
//两个有序链表不一定等长,多出来的直接接到新链表之后就可以
if(l1 != NULL){
last->next = l1;
}
if(l2 != NULL){
last->next = l2;
}

return result;
}

6、 编写代码,以给定值x为基准将链表分割成两部分,所有小于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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Node *partition(SList* head, int x){

SList *small;
SList *big;
SList *lastsmall;
SList *lastbig;

SList *node = head;
while(node != NULL){
if(node->value < x){
if(small == NULL){
small = smalllast =node;
}
else{
lastsmall->next = node;
lastsmall = node; // lastsmall表示的是最后一个节点,它等于node说明他就是最后一个结点,因为node每次将判断好的结点放在最后一个位置
}
}
else{
if(big == NULL){
big = lastbig =node;
}
else{
lastbig->next = node;
lastbig = node;
}
}
node = node->next;
}
if(lastsmall != NULL){
//如果比x小的结点存在,则该链表最后接上big链表
lastsmall->next = big;
}
if(lastbig != NULL){
//如果比x大的结点存在,则该链表最后指向NULL
lastbig->next = NULL;
}
if(lastsmall != NULL){
return small;
}
else{
return big;
}
}

7、在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。

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
Node *deleteDuplication(SList* head){
if(head == NULL){
return NULL;
}
SList *fake = (Node*)malloc(sizeof(Node));//先定义一个假结点
fake->next = head;

SList *prev = fake;
SList *p1 = head;
SList *p2 = head->next;
while(p2 != NULL){//不要忘了判断,否则p2为空后继续走,将会发生内存泄漏
//前后指针,一个在前走,一个在后走,在前走的同时判断有没有重复的
if(p1->val != p2->val){
prev = p1;
p1 = p2;
p2 = p2->next;
}
else{
while(p2 != NULL && p1->val == p2->val){
p2 = p2->next;
}
SList *cur = p1;
while(cur != p2){
SList *next = cur->next;
free(cur);
cur = next;
}
prev->next = p2;//很关键的一步,删完之后继续连接未删除的
p1 = p2;
if(p2 != NULL){
p2 = p2->next;
}
}
}
head = fake->next;
//prev在链表中一直相当于记录,就是fake
free(fake);
return head;
}

8、对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

1
1->2->2->1

思路还是很好理解的

1、找到中间结点

2、从中间结点开始往后逆转整个链表

3、将头结点和逆转数组作比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode *middleNode(ListNode *head){
if(head == NULL){
return NULL;
}
ListNode *slow = head;
ListNode *fast = head;

while(1){
fast = fast->next;
if(fast == NULL){
break;
}
slow = slow->next;
fast = fast->next;
if(fast == NULL){
break;
}
}
return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode *reverlist(ListNode *head){
if(head == NULL){
return NULL;
}
ListNode *result = NULL;
ListNode *cur = head;

while(cur != NULL){
ListNode *next = cur->next;

cur->next = result;
result = cur;

cur = next;
}
return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool chkPalindrome(ListNode* A){
ListNode *middle = middleNode(A);
ListNode *r = reverselist(middle->next);

ListNode *n1 = A, *n2 = r;
while(n1 != NULL && n2 != NULL){
if(n1->val != n2->val){
return false;
}
n1 = n1->next;
n2 = n2->next;
}
return true;
}
-------------The End-------------