876. 链表的中间结点

给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。

  1. 示例 1:

    1
    2
    3
    4
    5
    输入:[1,2,3,4,5]
    输出:此列表中的结点 3 (序列化形式:[3,4,5])
    返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
    注意,我们返回了一个 ListNode 类型的对象 ans,这样:
    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
  2. 示例 2:

    1
    2
    3
    输入:[1,2,3,4,5,6]
    输出:此列表中的结点 4 (序列化形式:[4,5,6])
    由于该列表有两个中间结点,值分别为 34,我们返回第二个结点。
  • 提示:

    给定链表的结点数介于 1 和 100 之间。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 思路:快慢指针,定义左右两个指针,右边的走两步,左边的走一步,遍历完,左边走一半。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode left = head;
ListNode right = head;
int count = 0;
while(right.next!=null){
right=right.next;
count++;
if(count==2){
left=left.next;
count=0;
}
}
if(count!=0){
left=left.next;
}
return left;
}
}

19. 删除链表的倒数第 N 个结点

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

  1. 示例 1:
    删除链表的倒数第 N 个结点

    1
    2
    输入:head = [1,2,3,4,5], n = 2
    输出:[1,2,3,5]
  2. 示例 2:

    1
    2
    输入:head = [1], n = 1
    输出:[]
  3. 示例 3:

    1
    2
    输入:head = [1,2], n = 1
    输出:[1]
  • 提示:

    1
    2
    3
    4
    链表中结点的数目为 sz
    1 <= sz <= 30
    0 <= Node.val <= 100
    1 <= n <= sz

题 解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 参考官方解答。
// 此时判断,若fast跑到尾结点,则删去的是头结点。
// 否则当fast跑到尾结点时,slow所指向的后一个结点就是我们要删除的结点。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* ret = malloc(sizeof(struct ListNode));
ret -> val = 0, ret -> next = head;
struct ListNode* slow = ret;
struct ListNode* fast = head;
//让fast先跑n个结点
for(int i = 0;i<n;++i){
fast = fast -> next;
}

while(fast){
fast = fast -> next;
slow = slow -> next;
}
//删去结点
slow->next = slow->next->next;
//ret指向的时头原来的头结点,返回时ret->next
return ret -> next;
}