Lei's Blog

链表

删除链表中的节点

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list – head = [4,5,1,9], which looks like following:

Example 1:

1
2
3
4
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list
should become 4 -> 1 -> 9 after calling your function.

Example 2:

1
2
3
4
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list
should become 4 -> 5 -> 9 after calling your function.

Note:

  • The linked list will have at least two elements.
  • All of the nodes’ values will be unique.
  • The given node will not be the tail and it will always be a valid node of the linked list.
  • Do not return anything from your function.
  • C

这道题的意思是删除一个节点,并没有指定是那个节点。
中文翻译是有偏差的,所以直接使用英文题干

删除节点,我们首先要找一个根节点,由于形参中没有给出,所以需要我们自己伪造一个 将指针变量 node 作为一个根节点,然后删除他之后的节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode *LinkList;
void deleteNode(struct ListNode* node) {
LinkList p;
node -> val = node -> next -> val; // 将Node的下一个节点赋值给node 是为了记录删除的是那个节点
p = node->next;
node -> next = node -> next ->next;
free(p);
}

删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
  • 说明:
    给定的 n 保证是有效的。

  • 进阶:
    你能尝试使用一趟扫描实现吗?

  • C

实现原理
使用双指针的方法, 定义指针 first sec 先使first正向移动n个位置 然后同时移动 first sec, 当firstnext指针指向空时,sec指针为指向要删除元素的上一个元素。
例如 10 个元素 删除倒数第8个 倒数第8个即为数字3 先正向移动到first到 8 ,然后 sec移动到2。 所以要删除的元素即为2的下一个元素。sec -> next = sec -> next -> next;

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode *Node;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
Node first = head;
Node sec = head;
while (n-- >0) {
first = first -> next;
}
if (!first) {
return head->next;
}
while (first -> next != NULL) {
sec = sec -> next;
first = first -> next;
}
sec -> next = sec -> next -> next;
return head;
}