力扣关于链表这部分基础算法还是较为简单和基础的
没有特殊说明的情况下，链表节点类型为：
struct ListNode { int val; struct ListNode *next; };同时，需要注意，默认的头指针
head->val域即第一个元素。
删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 – head = [4,5,1,9]，它可以表示为:
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
代码:
这个题目很容易理解偏差。其实就是让你把给你的节点删掉罢了。
void deleteNode(struct ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
代码:
采用快慢指针的思路。设置指针p和q：
- 一开始，
p和q都指向头节点； q指针现后移至p指针后的第n个位置，也就是q指针始终比p指针快n个，需要注意如果q还未移动n就已经是NULL了那么删去头节点就结束了；p=p->next同时q=q->next直到q->next==NULL，此时p->next就是要删除的节点。
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *p, *q;
p = head; q = head;
int i;
for (i = 0; i < n; i++) {
if (q->next == NULL) {
head = head->next;
return head;
}
q = q->next;
}
while (q->next!=NULL) {
q = q->next;
p = p->next;
}
p->next = p->next->next;
return head;
}
反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
代码:
三指针原地逆转。
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL) return NULL;
struct ListNode *h,*p,*c;
h = head;
p = h->next;
// 如果此时只有一个节点
if (p == NULL) return head;
c = p->next;
// 如果只有两个节点
if (c == NULL) {
p->next = h;
h->next = NULL;
return p;
}
// 三节点及以上情况
while (c != NULL) {
p->next = h;
h = p;
p = c;
c = c->next;
}
p->next = h;
head->next = NULL;
head = p;
return head;
}
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
代码:
判断大小拆指针重连。
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL && l2 == NULL) return NULL;
if (l1 == NULL && l2 != NULL) return l2;
if (l1 != NULL && l2 == NULL) return l1;
struct ListNode *p1, *p2, *newhead, *q;
p1 = l1;
p2 = l2;
newhead = (l1->val <= l2->val) ? l1 : l2;
q = newhead;
if (newhead == p1) p1 = p1->next;
else p2 = p2->next;
while (p1&&p2) {
if (p1->val <= p2->val) {
q->next = p1;
p1 = p1->next;
q = q->next;
}
else {
q->next = p2;
p2 = p2->next;
q = q->next;
}
}
if (p1) q->next = p1;
if (p2) q->next = p2;
return newhead;
}
回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
代码:
将链表数值写入数组，然后判断数组是否是回文数组。
bool isPalindrome(struct ListNode* head) {
if (head == NULL || head->next == NULL) return true;
// 计算链表长度
struct ListNode *p = head;
int len = 0;
while (p) {
p = p->next;
len++;
}
// 将链表复制到数组中
int *temparr = (int*)malloc(sizeof(int)*len);
int i = 0;
for (p = head; i < len; i++) {
temparr[i] = p->val;
p = p->next;
}
// 判断数组
int q = 0;
bool ispld = true;
for (; q < (len - q - 1); q++) {
if (temparr[q] != temparr[len - q - 1]) {
ispld = false;
break;
}
}
return ispld;
}
环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
代码:
使用快慢指针。始终有p=p->next同时q=q->next->next，这样可以保证如果链表中有环，指针p和q一定能相遇。
bool hasCycle(struct ListNode *head) {
struct ListNode *p, *q;
p = head;
q = head;
if (p == NULL) return false;
while (p!=NULL&&q!=NULL) {
if(q->next==NULL)return false;
if(q->next->next==NULL)return false;
p = p->next;
q = q->next->next;
if (p == q) {
return true;
}
}
return false;
}