题目描述

用【双指针法】删除链表中倒数第k个节点

代码部分

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode findKthToTail(ListNode pListHead, int k) {
        //参数的合法性判断
        if(pListHead == null || k < 1) return pListHead;

        //k的范围判断
        ListNode cur = pListHead;
        int len = 0;
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        if(len < k) return null;

        //定义虚拟头节点
        ListNode dummyhead = new ListNode(0);
        dummyhead.next = pListHead;

        ListNode fast = dummyhead;
        ListNode slow = dummyhead;

        //fast先走k+1步
        k++;
        while(k-- > 0 && fast != null) {
            fast = fast.next;
        }

        //之后fast和slow同时移动
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        //删除倒数第k个结点 slow指向目标元素的前一个位置
        ListNode res = slow.next;
        slow.next = slow.next.next;

        return res;
    }
}