首页 > 代码库 > 【LeetCode】19. Remove Nth Node From End of List
【LeetCode】19. Remove Nth Node From End of List
题目:
思路:如果链表为空或者n小于1,直接返回即可,否则,让链表从头走到尾,每移动一步,让n减1。
1.链表1->2->3,n=4,不存在倒数第四个节点,返回整个链表
扫过的节点依次:1-2-3
n值得变化:3-2-1
2.链表1->2->3,n=3
扫过的节点依次:1-2-3
n值得变化:2-1-0
3.链表1->2->3,n=2
扫过的节点依次:1-2-3
n值得变化:1-0--1
当走到链表结尾时:1.n>0,说明链表根本没有第n个节点,直接返回原链表;
2.n=0,说明链表倒数第n个节点就是头结点,返回head.next;
3.n<0,重新从头结点开始走,没移动一步让n加1,当n=0时,移动停止,当前移动到的节点就是要删除节点的前一个节点。因为如果链表长度是L,则倒数第n个节点的前一个结点就是L-n。第一次扫到链表末尾时,n的值变成n-L,当n不断加1直到为0时,第二次扫到的位置正好是第L-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) { if(head==null||n<1){ return head; } ListNode cur=head; while(cur!=null){ n--; cur=cur.next; } if(n==0){ return head.next; } if(n<0){ cur=head; while(++n!=0){//当n=0时移动停止,移动到的节点就是要删除节点的前一个节点 cur=cur.next; } cur.next=cur.next.next; } return head; } }
【LeetCode】19. Remove Nth Node From End of List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。