# 移出链表元素
给你一个无头单向不循环链表的首结点l和一个整数 val ，请你删除链表中所有等于 val 的节点，并返回新的首结点 。
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
| /*
struct llist_node
{
int val;
struct llist_node *next;
};
*/
struct llist_node* removeElements(struct llist_node* l, int val)
{
struct llist_node* cur = l;//指向要删除的结点
struct llist_node* back = NULL;//指向要删除的结点的前一个位置
while(cur != NULL)//判断是否遍历完所有结点
{
if(cur->val == val)//判断当前指向的结点是否是要删除的结点
{
if(back == NULL)//判断删除的是否是链表的首结点
{
l = cur->next;//让l指针指向下一个结点
free(cur);//释放首结点
cur = l;//让cur指针指向新的首结点
}
else//如果删除的不是首结点就按照普通的删除方法进行
{
back->next = cur->next;
free(cur);
cur = back->next;
}
}
else//如果不是要删除的结点，找下一个结点
{
back = cur;
cur = cur->next;
}
}
return l;//返回指向首结点的指针l
}
|
# 反转链表
给你一个无头单向不循环链表的首结点l ，请你反转链表，并返回反转后的链表首结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| /*
struct llist_node
{
int val;
struct llist_node *next;
};
*/
struct llist_node* reverseList(struct llist_node* l)
{
struct llist_node *cur = l;//cur指针指向当前操作的结点
struct llist_node *p = NULL;//p指针指向原链表中cur的下一个位置
struct llist_node *next = NULL;//next指针指向反转链表后cur的下一个位置
while(cur != NULL)//判断是否遍历完整个链表
{
p = cur->next;//p指针指向原链表中cur的下一个位置
cur->next = next;//让cur指针指向的结点的next指向前一个位置
next = cur;//移动next
cur = p;//移动cur
}
return next;
}
|
# 链表的中间结点
给定一个头结点为handler的单向不循环链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /*
struct llist_node
{
int val;
struct llist_node *next;
};
*/
//快慢指针
//慢指针一次走一步，慢指针一次走两步
struct llist_node* middleNode(struct llist_node* handler)
{
struct llist_node *s = handler;//慢指针
struct llist_node *f = handler;//快指针
while(f != NULL && f->next != NULL)
{
s = s->next;
f = f->next->next;
}
return s;
}
|
# 链表中倒数第k个结点
给定一个头结点为handler的单向不循环链表，输出该链表中倒数第k个结点。
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
| /*
struct llist_node
{
int val;
struct llist_node *next;
};
*/
//先让一个指针走k个结点，再让另外一个指针跟着走
struct llist_node* FindKthToTail(struct llist_node* handler, int k)
{
struct llist_node *s = handler;
struct llist_node *f = handler;
while(k--)
{
if(f == NULL)//判断k值是否大于链表节点数
return NULL;
f = f->next;
}
while(f != NULL)
{
s = s->next;
f = f->next;
}
return s;
}
|
# 合并两个有序链表
将两个升序的无头单向不循环链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
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
| /*
struct llist_node
{
int val;
struct llist_node *next;
};
*/
struct llist_node* mergeTwoLists(struct llist_node* l1, struct llist_node* l2)
{
struct llist_node *l = NULL;
struct llist_node *cur = NULL;
if(l1 == NULL)//判断l1链表是否不存在
return l2;
if(l2 == NULL)//判断l2链表是否不存在
return l1;
if(l1->val < l2->val)
{
l = cur = l1;
l1 = l1->next;
}
else
{
l = cur = l2;
l2 = l2->next;
}
while(l1 != NULL && l2 != NULL)
{
if(l1->val < l2->val)
{
cur->next = l1;
l1 = l1->next;
}
else
{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if(l1 == NULL)
cur->next = l2;
else
cur->next = l1;
return l;
}
|
# 链表分割
现有一无头单向不循环链表的首结点指针l，给一定值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
| /*
struct llist_node
{
int val;
struct llist_node *next;
};
*/
struct llist_node* partition(struct llist_node* l, int x)
{
struct llist_node *cur = l;
struct llist_node *minhead = NULL;
struct llist_node *maxhead = NULL;
struct llist_node *mincur = NULL;
struct llist_node *maxcur = NULL;
minhead = malloc(sizeof(struct llist_node));
maxhead = malloc(sizeof(struct llist_node));
minhead->next = maxhead->next = NULL;
mincur = minhead;
maxcur = maxhead;
while(cur != NULL)
{
if(cur->val < x)
{
mincur->next = cur;
mincur = mincur->next;
}
else
{
maxcur->next = cur;
maxcur = maxcur->next;
}
cur = cur->next;
}
mincur->next = maxhead->next;
maxcur->next = NULL;
l = minhead->next;
free(minhead);
free(maxhead);
return l;
}
|
# 链表的回文结构
`现有一无头单向不循环链表的首结点指针l，请返回一个bool值，代表其是否为回文结构。`
# 环形链表
`给你一个单向链表的头结点 head ，判断链表中是否有环。`
# 单向不循环链表的排序
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
| /*
struct llist_node
{
int val;
struct llist_node *next;
};
*/
struct llist_node *pop_sort(struct llist_node *l)
struct llist_node *p, *q, *tail;
tail = NULL;
while((l->next->next) != tail)
{
p = l;
q = l->next;
while(q->next != tail)
{
if((q->val) > (q->next->val))
{
p->next = q->next;
q->next = q->next->next;
p->next->next = q;
q = p->next;
}
q = q->next;
p = p->next;
}
tail = q;
}
}
|