1. 移除链表元素
题目描述
解题思路
这道题较好的解法是创建一个新链表, 把不等于val的节点链接到一起, 然后返回新链表的头结点
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* cur = head;
struct ListNode* tail = NULL;
struct ListNode* newnode = NULL;
while (cur)
{
if (cur->val != val)
{
if (tail == NULL)
{
newnode = cur;
tail = newnode;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
}
if (tail != NULL)
{
tail->next = NULL;
}
return newnode;
}这里需要处理两种特殊情况，链表为空和删除链表所有元素
最后把最后一个节点的next赋值为NULL
2. 找链表的中心节点
题目描述
解题思路
快慢指针, 慢指针一次走一步, 快指针一次走两步, 当快指针走完, 慢指针会指向中心节点，所以最后返回慢指针也就找到了中心节点
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}这道题需要注意的一个点, 这道题的循环必须这样写 while (fast && fast->next), 分别判断偶数个节点, 奇数个节点的情况, 避免发生访问空指针的情况
3. 找链表倒数第K个节点
题目描述
解题思路
因为倒数第K个节点跟最后一个节点之间的距离是K-1步，如k=3, 倒数第三个节点与最后一个节点之间的距离是2
所以可以用快慢指针的解法, 让fast先走k-1步, 然后同时走, 当fast走到最后一个节点的时候, slow指向的节点就是倒数第K个节点
struct ListNode* getKthFromEnd(struct ListNode* head, int k){
struct ListNode* fast = head;
struct ListNode* slow = head;
// 快指针先走k-1步
while (k-1)
{
fast = fast->next;
k--;
}
// 同时走
while (fast->next)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
4. 反转链表
题目描述
解题思路
三指针
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* prev = NULL, *next = NULL;
struct ListNode* cur = head;
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
5. 合并两个有序列表
题目描述
解题思路
创建一个带哨兵位的头节点, 然后取小的尾插, 最后将没有走完的节点直接尾插
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* ptr1 = list1, *ptr2 = list2;
struct ListNode* guard, *tail;
guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
guard->next = NULL;
while (ptr1 && ptr2)
{
if (ptr1->val < ptr2->val)
{
tail->next = ptr1;
ptr1 = ptr1->next;
tail = tail->next;
}
else
{
tail->next = ptr2;
tail = tail->next;
ptr2 = ptr2->next;
}
}
if (ptr1)
{
tail->next = ptr1;
}
if (ptr2)
{
tail->next = ptr2;
}
struct ListNode* head = guard->next;
free(guard);
return head;
}因为guard指向的空间是动态开辟的, 所以一定要释放, 避免内存泄漏
6. 分割链表
题目描述
解题思路
这道题最简单的解法就是创建两个新链表, 将所有大于, 小于x的节点分别尾插到两个不同链表上, 最后链接起来
struct ListNode* partition(struct ListNode* head, 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 = head;
while (cur)
{
if (cur->val < x)
{
Ltail->next = cur;
Ltail = Ltail->next;
}
else
{
Gtail->next = cur;
Gtail = Gtail->next;
}
cur = cur->next;
}
Gtail->next = NULL;
Ltail->next = Gguard->next;
struct ListNode* newhead = Lguard->next;
free(Lguard);
free(Gguard);
return newhead;
}
7. 回文链表
题目描述
解题思路
首先找到链表的中心节点, 然后逆置，最后进行判断
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* FindMidNode(struct ListNode* head)
{
// 快慢指针
struct ListNode* fast = head, *slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
struct ListNode* ListReverse(struct ListNode* mid)
{
struct ListNode* cur = mid, *prev = NULL;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
bool isPalindrome(struct ListNode* head){
// 找中心节点
struct ListNode* mid = FindMidNode(head);
// 逆序
struct ListNode* rhead = ListReverse(mid);
// 判断
while (head && rhead)
{
if (head->val != rhead->val)
{
return false;
}
else
{
head = head->next;
rhead = rhead->next;
}
}
return true;
}
8. 相交链表
题目描述
解题思路
第一步, 找尾, 其次分别计算出链表A，B的长度
第二步, 如果尾不同, 表示链表不相交, 退出。 如果尾相同链表相交, 开始找起始节点
第三步, 根据链表A，B的长度, 找到差距步, 然后让长的链表先走差距步
最后, 同时走, 循环结束即找到起始节点
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* tailA = headA, *tailB = headB;
int lenA = 0, lenB = 0;
// 找尾, 分别计算出链表A，B的长度
while (tailA)
{
lenA++;
tailA = tailA->next;
}
while (tailB)
{
lenB++;
tailB = tailB->next;
}
// 如果尾节点不同表示链表不相交
if (tailA != tailB)
return NULL;
// 链表相交, 找起始节点
struct ListNode* longList = headA, *shortList = headB;
int gap = 0;
if (lenA > lenB)
{
longList = headA;
shortList = headB;
gap = lenA - lenB;
}
if (lenA < lenB)
{
longList = headB;
shortList = headA;
gap = lenB - lenA;
}
// 让长链表先走差距步
while (gap--)
{
longList = longList->next;
}
// 然后同时走, 进而判断相交节点
while (longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
return longList;
}标签：head,单链,ListNode,struct,cur,next,链表,解析,OJ From： https://www.cnblogs.com/xumu11291/p/17239673.html