首页 > 代码库 > 19. Remove Nth Node From End of List

19. Remove Nth Node From End of List

2024-09-28 05:59:39   219人阅读

一、描述

　　1、题目

　　　　　　技术分享

　　2、题意

　　　　一个只能顺序遍历的链表，求去除逆序数为 n 的节点后的链表并返回!

 

二、解答

　　　　1、思路：

　　　　　　　　首先想到遍历一次链表，为求出节点总个数 ，则要删除的节点序号即为： 节点总数 - 逆序号n ，问题得解！

　　

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // index start from 1
        if(head.next == null)
            return null;
        int index = 1;
        ListNode tempNode = head;
        while(tempNode.next != null) {
            tempNode = tempNode.next;
            index++;
        }
        
        // realIndex start from 0
        int realIndex = index - n;
        if(realIndex == 0) {
            head = head.next;
            return head;
        }
        tempNode = head;
        // so index should start from 0
        index = 1;
        while(tempNode != null && tempNode.next != null) {
            if(index == realIndex) {
                 if(tempNode.next != null)
                    tempNode.next = tempNode.next.next;
                break;
            }
            index++;
            tempNode = tempNode.next;
        }
        
        return head;
    }
}

 

2、优化：

　　　　不是双向链表，求逆序号的节点，可以采用一个指针指向表头p1，另一个指针p2向后移动，当两指针距离达到 n 时，p1开始和 p2 一起移动，当p2移动到链表末尾，p1即为所要删除的节点!

　　

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        if(head.next == null)
            return null;
        
        int distant = 1;
        ListNode slow = head, fast = head;

        // distant = n - 1
        while(distant++ < n) 
            fast = fast.next;
        
        // keep the distant = n 
        if(fast == null) 
            return head.next;
        else if(fast.next != null)
            fast = fast.next;
        else 
            // remove Node slow 
            return slow.next;
            
        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        
        slow.next = slow.next.next;
        
        return head;
    }
}

三、总结

　　　　这种距离的题目做过很多次，但现在还没有首先反应出采用两个指针计算距离，看来还是太年轻！其中中间很多边缘情况需要考虑，要细心想明白！删除第 n 个逆序元素，p1 指向的应当是 distant=n+1 的指针才能进行删除！这种题最好画节点图！

19. Remove Nth Node From End of List


联系
我们