题目描述

题目1（876. 链表的中间结点）

题目2（19 删除链表的倒数第 N 个结点）

解题思路

题目1（876. 链表的中间结点）

• 思路一：遍历链表统计节点个数，然后返回中间位置节点。
• 思路二：使用两个指针分别从表头开始遍历，其中一个指针（one）每次向后移动一位，另一个指针（two）每次向后移动两个位置。当two指针移动至表尾时，one指针所指就为中间节点，返回one。

题目2（19 删除链表的倒数第 N 个结点）

使用两个指针（front、back）遍历链表，先让front指针向后移动n位，然后再让两个指针一起移动。遍历结束时，删除back指针后面的节点即可。

代码实现

题目1（876. 链表的中间结点）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode one = head, two = head;
        while(two != null && two.next != null){
            one = one.next;        //后移一位
            two = two.next.next;    //后移两位
        }
        return one;
        
        // 统计节点个数解法
        // int count = 0;
        // ListNode temp = head;
        // while(head.next != null){
        //     ++count;
        //     head = head.next;
        // }
        // int mid = (count+1) / 2;
        // for(int i=0;i<mid;i++){
        //     temp = temp.next;
        // }
        // return temp;
    }
}

题目2（19 删除链表的倒数第 N 个结点）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //如果只有头结点或头结点为null直接返回
        if(head == null || head.next == null) return null;
        ListNode temp = new ListNode(0, head);
        ListNode front = head, back = temp;
        for(int i = 0;i<n;i++){
            front = front.next;    //front先移动n位
        }
        while(front != null){
            front = front.next;
            back = back.next;    //front、back一起移动
        }
        back.next = back.next.next;        //删除back后面的一个节点

        return temp.next;
    }
}