首页 > 代码库 > leetcode------Remove Nth Node From End of List

leetcode------Remove Nth Node From End of List

2024-11-14 06:41:02   203人阅读

标题：Remove Nth Node From End of List
通过率：28.5%
难度：简答

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

这个题说的很明确就是删除最后面数一个节点，我刚开始时没有去考虑只能遍历一遍，我先查一遍有几个，然后去删除，其中要考虑删的是头结点和尾节点，

代码看着也比较复杂，如下：

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode removeNthFromEnd(ListNode head, int n) {14         int len=1;15         ListNode temp=head;16         ListNode result=head;17 18         if(head==null)return null;19         while(temp.next!=null){20             len++;21             temp=temp.next;22         }23         if(len==1)return null;24         if(n==len){25             head=head.next;26             return head;27         }28         for(int i=0;i<len-n-1;i++){29             head=head.next;30         }31         if(head.next.next==null){32             head.next=null;33         }else{34             head.next=head.next.next;35         }36         37         return result;38     }39 }

然后我想不起来怎么一趟，我去网上查找时发现了还是用两个指针，我一下想起来怎么做了，前面做过一个找链表的环的题目，一遍这种去遍历的问题如果说时间复杂度为O（n）或者说只能遍历一遍的话基本都是去考虑两个指针，先跑那个指针到结尾，后跑那个指针到要删除那个节点的前一个节点，两个指针中间相差N，但是如果要删除的元素是头结点就要另外去处理了，由于指针相差n步，所以如果是删除的头结点那么先跑的指针要跑到结尾后往下走，利用这个越界的问题来处理头指针，如果头指针在往后跑时遇到了next为空就说明要删除的是头结点，直接返回head。next就行了。

具体代码如下：

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode removeNthFromEnd(ListNode head, int n) {14         ListNode first=head,second=head;15         for(int i=0;i<n;i++){16             if(second.next==null){17                 head=head.next;18                 return head;19             }20             second=second.next;21         }22         while(second.next!=null){23              second=second.next;24              first=first.next;25         }26         first.next=first.next.next;27         return head;28         29     }30 }

 

leetcode------Remove Nth Node From End of List


联系
我们