当前位置 : 主页 > 手机开发 > ROM >

LeetCode -- 19. Remove Nth Node From End of List

来源:互联网 收集:自由互联 发布时间:2021-06-10
题意及思路 题意:略(注:题意问你能否只一遍遍历,找到要删除的节点?) 思路:@一开始的愚蠢方法,也没看到题目的注释。用的头插法反转单链表。。。很愚蠢的方法,详细见代

分享图片

 

题意及思路

题意:略(注:题意问你能否只一遍遍历,找到要删除的节点?)

思路:@一开始的愚蠢方法,也没看到题目的注释。用的头插法反转单链表。。。很愚蠢的方法,详细见代码1。@得高人指点后,用的方法是双指针法。思路大致是:

 

代码1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode top = new ListNode(Integer.MIN_VALUE);
        top.next = head;
        ListNode p = top;
        if(n==1){
            while(p.next.next!=null) p = p.next;
            p.next = null;
            return top.next;
        }
        top = reverseList(head);
        p = top.next;
        int id = 0;
        while(p!=null){
            if(++id==n-1){
                if(p.next!=null) p.next = p.next.next;
                else p.next = null;
            }
            p = p.next;
        }
        return reverseList(top.next).next;
    }
    
    private ListNode reverseList(ListNode head){
        ListNode top = new ListNode(Integer.MIN_VALUE);
        top.next = null;
        ListNode t,p=head;
        while((t=p)!=null){
            p = p.next;
            t.next = top.next;
            top.next = t;
        }
        return top;
    }
}

 

代码2

网友评论