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

一颗蔬菜 2019-09-08 PM 55℃ 0条

原题链接

我的思路:遍历整个链表求出链表长度。再次遍历整个链表,当遍历到倒数第N个时,原地删除该节点。这种朴实无华的思路写出来的代码一般都是超出时间限制

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }  1 2 3 null
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode curr = head; 
        int index = 0;
        while (curr.next != null) {
            curr = head.next;
            index ++;
        }
        ListNode res = head;
        for (int i = 0; i <= index; i++) {
            if (i == index - n + 1) {
                head.val = head.next.val;
                head.next = head.next.next;
                break;
            }
            head = head.next;
        }
        return res;
        
    }
}

我们来康康大佬们都是怎么想的吧。

双指针法,让后指针先走N步,然后双指针一起移动,当后指针的next等于null时,删除前节点的next节点。要注意删除头结点的情况。

public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode preNode = head;              
    ListNode curNode = head;                     
                                                    
    for (int i = 0; i < 3; i++) {
        curNode = curNode.next;
    }
    
    // 删除倒数最后一个节点  也就是头结点
    if (curNode == null) {
        return preNode.next;
    }

    while (curNode.next != null) {
        preNode = preNode.next;
        curNode = curNode.next;
    }

    preNode.next = preNode.next.next;
    return head;
}
标签: 算法

非特殊说明,本博所有文章均为博主原创。