[LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点
2023-09-27 14:28:37 时间
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.
移除给定链表的倒数第n个节点,n总是有效的,要求一次遍历完成one pass。
解法1: two pass,先求出链表的总长度,然后在删除node
解法2:双指针,经典题。主要是在一个遍历中找到第n个倒数元素,一个指针先走n步,然后两个指针同步走,直到第一个走到终点,第二个指针指向的就是需要删除的节点。Corner case: head == null; 头节点的处理,比如,1->2->NULL, n =2; 这时,要删除的就是头节点。
Java: Naive Two Pass
public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return null; //get length of list ListNode p = head; int len = 0; while(p != null){ len++; p = p.next; } //if remove first node int fromStart = len-n+1; if(fromStart==1) return head.next; //remove non-first node p = head; int i=0; while(p!=null){ i++; if(i==fromStart-1){ p.next = p.next.next; } p=p.next; } return head; }
Java:
public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return null; ListNode fast = head; ListNode slow = head; for(int i=0; i<n; i++){ fast = fast.next; } //if remove the first node if(fast == null){ head = head.next; return head; } while(fast.next != null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head; }
Python:
class ListNode: def __init__(self, x): self.val = x self.next = None def __repr__(self): if self is None: return "Nil" else: return "{} -> {}".format(self.val, repr(self.next)) class Solution: # @return a ListNode def removeNthFromEnd(self, head, n): dummy = ListNode(-1) dummy.next = head slow, fast = dummy, dummy for i in xrange(n): fast = fast.next while fast.next: slow, fast = slow.next, fast.next slow.next = slow.next.next return dummy.next
C++:
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if (!head->next) return NULL; ListNode *pre = head, *cur = head; for (int i = 0; i < n; ++i) cur = cur->next; if (!cur) return head->next; while (cur->next) { cur = cur->next; pre = pre->next; } pre->next = pre->next->next; return head; } };
All LeetCode Questions List 题目汇总
相关文章
- Leetcode: Plus One Linked List
- Leetcode: Palindrome Linked List
- Leetcode: Reverse Linked List II
- Leetcode: Integer to Roman
- leetCode 86.Partition List(分区链表) 解题思路和方法
- 【leetcode】14. longest common prefix
- [LeetCode] Insertion Sort List
- [LeetCode] Clone Graph
- [LeetCode] Add Two Numbers(stored in List)
- 【LeetCode】61. Rotate List
- 【Leetcode】Linked List Cycle II
- [LeetCode] 1290. Convert Binary Number in a Linked List to Integer 二进制链表转整数
- [LeetCode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
- [LeetCode] 876. Middle of the Linked List 链表的中间结点
- [LeetCode] 426. Convert Binary Search Tree to Sorted Doubly Linked List 将二叉搜索树转为有序双向链表
- [LeetCode] 382. Linked List Random Node 链表随机结点
- [LeetCode] Move Zeroes 移动零
- [LeetCode] 61. Rotate List 旋转链表
- [LeetCode] Partition List 划分链表
- [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二
- leetcode 769. Max Chunks To Make Sorted 最多能完成排序的块(中等)
- leetcode 142. Linked List Cycle II 环形链表 II