题目一 反转链表
还是先画图给大家看看
用头插的方法将链表反转，首先定义一个新链表newhead，再定义一个cur来控制原链表走向下一个位置
1.将cur头插到newhead
2.将cur赋予newhead
3.cur走到他的下一个位置
循环到cur为NULL截至
看代码：
struct ListNode { int val; struct ListNode* next; }; struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* cur = head; while (cur) { struct ListNode* next = cur->next;//保存下一个位置 cur->next = newhead;//头插到newhead newhead = cur;//更新头节点 cur = next; } return newhead; }
题目二 链表的中间节点
这道题目就是一个经典的快慢指针问题
我们可以设置两个指针
慢指针先走 每次走一格
快指针再走 每次走两格
当快指针指向最后一个节点或者是空指针的时候直接return slow就可以
还是画图理解
看代码：
struct ListNode { int val; struct ListNode* next; }; struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = NULL, * fast = NULL; slow = fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
很简单 大家领悟一下思路就可以
题目三 链表的倒数第K个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
来源：力扣（LeetCode）
还是一个快慢指针的问题
这里要求倒数k个位置
只需要让fast先走k步就可以
放fast走到NULL的时候return solw的值
当然这里要注意 如果说fast走到了NULL k还没有归零
那么这个时候就要返回空指针了
代码表示如下
struct ListNode { int val; struct ListNode* next; }; int kthToLast(struct ListNode* head, int k) { struct ListNode* slow = NULL, * fast = NULL; slow = fast = head; while (k--) { if (fast == NULL) { return NULL; } fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } return slow->val; }
题目四 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
这题的话我们可以用哨兵位头节点可以忽略很多问题
什么是哨兵节点？
哨兵在前面，作为一个链表的头，随时可以找到链表的头节点
对速度没有什么帮助，常常搭配双指针，可以使得尾插变得调理清晰
尾插的过程中，不必将首个元素插入变得复杂
看图理解一下
1.开辟一个哨兵位节点，以及cur1，cur2分别指向俩个有序链表的头指针。
2.比较两个有序链表的每一位，小的尾插到哨兵位节点
3.判断有序链表是否为NULL
4.释放哨兵位节点（不可忽略）
看代码：
struct listnode { int val; struct listnode* next; }; struct listnode* mergetwolists(struct listnode* list1, struct listnode* list2) { struct listnode* cur1 = list1, * cur2 = list2; struct listnode* guard = null, * tail = null; guard = tail = (struct listnode*)malloc(sizeof(struct listnode)); tail->next = null; while (cur1 && cur2) { if (cur1->val < cur2->val) { tail->next = cur1; tail = tail->next; cur1 = cur1->next; } else { tail->next = cur2; tail = tail->next; cur2 = cur2->next; } } if (cur1) { tail->next = cur1; } if (cur2) { tail->next = cur2; } struct listnode* newhead = guard->next; free(guard); return newhead; }
