前言
leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点等的介绍
一、移除链表元素
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
ListNode* newhead = NULL;
ListNode* newtail = NULL;
ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
if(newhead == NULL)
{
newhead = newtail = cur;
}
else
{
newtail->next = cur;
newtail = newtail->next;
}
cur = cur->next;
}
else
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
}
if(newtail)
newtail->next = NULL;
return newhead;
}
- 遍历链表，若节点的值不等于给定的值，则尾插到新链表后面。
- 若等于，则跳过。
二、链表的中间节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* fast = head, *slow = head;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
- 快慢指针
- 快指针一次走两步。
- 慢指针一次走一步。
- 当快指针节点为空或者下一个节点为空时，跳出循环。
- 此时慢指针指向中间节点。
三、合并两个有序链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
if(list1 == NULL &&list2 == NULL)
{
return NULL;
}
ListNode* newHead , *newTail;
newHead = newTail = NULL;
while(list1 != NULL && list2 != NULL)
{
if(list1->val > list2->val)
{
if(newHead == NULL)
{
newHead = newTail = list2;
}
else
{
newTail->next = list2;
newTail = newTail->next;
}
list2 = list2->next;
}
else
{
if(newHead == NULL)
{
newHead = newTail = list1;
}
else
{
newTail->next = list1;
newTail = newTail->next;
}
list1 = list1->next;
}
}
if(list1 == NULL)
{
if(newHead == NULL)
newHead = list2;
else
newTail->next = list2;
}
else
{
if(newHead == NULL)
newHead = list1;
else
newTail->next = list1;
}
return newHead;
}
- 遍历两个单链表。
- 两个链表都不为空，判断节点大小，将小点节点尾插到新的头节点上。
- 若有一个链表为空，跳出循环，并将另一个链表尾插到新的尾节点上。
四、反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
if(head == NULL)
return NULL;
ListNode* n1, *n2, *n3;
n1 = NULL;
n2 = head;
n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}
return n1;
}
-
- 将每个节点的next指向前一个节点。
-
- 创建一个新的头节点，遍历链表进行头插。
五、链表分割
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* gGuard, *gTail, *lGuard, *lTail;
gGuard = gTail = (struct ListNode*)malloc(sizeof(struct ListNode));
lGuard = lTail = (struct ListNode*)malloc(sizeof(struct ListNode));
gGuard->next = lGuard->next = NULL;
struct ListNode* cur = pHead;
while(cur)
{
if(cur->val < x)
{
lTail->next = cur;
lTail = lTail->next;
}
else
{
gTail->next = cur;
gTail = gTail->next;
}
cur = cur->next;
}
lTail->next = gGuard->next;
gTail->next = NULL;
pHead = lGuard->next;
free(gGuard);
free(lGuard);
return pHead;
}
};
- 创建两个带有哨兵位的单向链表。
- 若小于给定值尾插到小的链表中。
- 若大于等于给定值尾插到大的链表中。
- 再将小链表的尾节点的next指向大链表的第一个有效节点。
- 最后再将大链表的尾节点的next指向NULL。
六、倒数第k个节点
输入一个链表，输出该链表中倒数第k个结点。
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode
{
int val;
struct ListNode* next;
}ListNode;
ListNode* FindKthToTail(ListNode* pListHead, int k)
{
if (pListHead == NULL)
{
return NULL;
}
ListNode* fast, * slow;
fast = slow = pListHead;
int i = 0;
for (i = 1; i < k; i++)
{
fast = fast->next;
if (fast == NULL)
{
return NULL;
}
}
while (fast->next != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
int main()
{
ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
ListNode* n2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* n3 = (ListNode*)malloc(sizeof(ListNode));
ListNode* n4 = (ListNode*)malloc(sizeof(ListNode));
ListNode* n5 = (ListNode*)malloc(sizeof(ListNode));
phead->val = 1;
n2->val = 2;
n3->val = 3;
n4->val = 4;
n5->val = 5;
phead->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = NULL;
ListNode* plist = phead;
ListNode* ret = FindKthToTail(plist,5);
while (ret)
{
printf("%d->", ret->val);
ret = ret->next;
}
printf("NULL\n");
return 0;
}
- 倒数第k个和倒数第一个之间的距离是k-1.
- 所以使用快慢指针，将快的指针先走k-1步，此时快慢指针差距是k-1.
- 所以当快指针走到链表结尾时，慢指针走到倒数第k个节点。
总结
leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点等的介绍