【算法】leetcode_19_双指针法应用于链表

地址:https://leetcode.com/problems/remove-nth-node-from-end-of-list/


// AC: Runtime: 1 ms, faster than 18.11% of Java online submissions for Remove Nth Node From End of List.
// Memory Usage: 36.7 MB, less than 89.53% of Java online submissions for Remove Nth Node From End of List.
// thought: using a faster node, moving forward n - 1 steps, and move forward together, 
//        and delete the node when faster node stops.
// T:O(n), S:O(1)
//
/**
 * 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) {
        ListNode headCopy = head;
        // 特殊处理, 因为在 n = 1 时,双指针的快指针根本不走,也就无法拿到要删除的 node 的前一个节点
        if (n == 1) {
            while (head.next != null && head.next.next != null) {
                System.out.println(head.val);
                head = head.next;
            }
            if (head.next == null) {
                return null;
            }
            head.next = null;
            return headCopy;
        }
        int forwardCount = n - 1;
        while (forwardCount-- > 0) {
            headCopy = headCopy.next;
        }
        ListNode headCopy2 = head;
        while (headCopy.next != null) {
            head = head.next;
            headCopy = headCopy.next;
        }
        // delete node
        head.val = head.next.val;
        head.next = head.next.next;

        return headCopy2;
    }
}


发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

«   2021年6月   »
123456
78910111213
14151617181920
21222324252627
282930
控制面板
您好,欢迎到访网站!
  查看权限
网站分类
搜索
最新留言
文章归档
网站收藏
友情链接

    Powered By Z-BlogPHP 1.5.2 Zero

    Copyright liuyang1.com. 转载文章,请注明出处。谢谢!