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

迈不过友情╰ 2023-01-01 07:57 106阅读 0赞

## Topic ##

*  Linked List
 *  Two Pointers

## Description ##

[https://leetcode.com/problems/remove-nth-node-from-end-of-list/][https_leetcode.com_problems_remove-nth-node-from-end-of-list]

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

**Follow up**: Could you do this in one pass?

**Example 1**:

1 -> 2 -> 3 -> 4 -> 5
    
    remove the second node from the end of the list
    
    1 -> 2 -> 3 -> 5
    
    Input: head = [1,2,3,4,5], n = 2
    Output: [1,2,3,5]

**Example 2**:

Input: head = [1], n = 1
    Output: []

**Example 3**:

Input: head = [1,2], n = 1
    Output: [1]

**Constraints**:

*  The number of nodes in the list is sz.
 *  1 <= sz <= 30
 *  0 <= Node.val <= 100
 *  1 <= n <= sz

## Analysis ##

方法一：我写的。

1.  指针a，b指向链头，然后b移动n步。
2.  b移动n步后，a、b指针齐步移，直到b指向Null。
3.  移除a所指向节点。
4.  返回链头。

方法二：别人写的，思路与方法一的相同。

## Submission ##

import com.lun.util.SinglyLinkedList.ListNode;
    
    public class RemoveNthNodeFromEndOfList { 
    
    	// 方法一：我写的
    	public ListNode removeNthFromEnd1(ListNode head, int n) { 
    		if (head == null || n <= 0)
    			return head;
    		int count = 1;
    		ListNode fakeHead = new ListNode(-1, head);
    		ListNode p1 = head, p2 = head.next, prev = fakeHead;
    
    		while (p2 != null && count < n) { 
    			p2 = p2.next;
    			count++;
    		}
    
    		if (n != count)
    			return fakeHead.next;// count > 链表长度的情况
    
    		// 齐步走
    		while (p2 != null) { 
    			prev = p1;
    			p1 = p1.next;
    			p2 = p2.next;
    		}
    
    		// 移除
    		prev.next = p1.next;
    		p1.next = null; // help GC
    
    		p2 = fakeHead.next;
    		fakeHead.next = null; // help GC
    
    		return p2;
    	}
    
    	// 方法二：别人写的
    	public ListNode removeNthFromEnd2(ListNode head, int n) { 
    
    		ListNode start = new ListNode(0);
    		ListNode slow = start, fast = start;
    		slow.next = head;
    
    		// Move fast in front so that the gap between slow and fast becomes n
    		for (int i = 1; i <= n + 1; i++) { 
    			fast = fast.next;
    		}
    		// Move fast to the end, maintaining the gap
    		while (fast != null) { 
    			slow = slow.next;
    			fast = fast.next;
    		}
    		// Skip the desired node
    		slow.next = slow.next.next;
    		return start.next;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.SinglyLinkedList;
    import com.lun.util.SinglyLinkedList.ListNode;
    
    public class RemoveNthNodeFromEndOfListTest { 
    
    	@Test
    	public void test1() { 
    		RemoveNthNodeFromEndOfList obj = new RemoveNthNodeFromEndOfList();
    
    		ListNode original1 = SinglyLinkedList.ints2List(1, 2, 3, 4, 5);
    		ListNode expected1 = SinglyLinkedList.ints2List(1, 2, 3, 5);
    		assertTrue(SinglyLinkedList.areTwoListEqual(expected1, obj.removeNthFromEnd1(original1, 2)));
    
    		ListNode original2 = new ListNode(1);
    		assertNull(obj.removeNthFromEnd1(original2, 1));
    
    		ListNode original3 = SinglyLinkedList.ints2List(1, 2);
    		ListNode expected3 = new ListNode(1);
    		assertTrue(SinglyLinkedList.areTwoListEqual(expected3, obj.removeNthFromEnd1(original3, 1)));
    	}
    	
    	@Test
    	public void test2() { 
    		RemoveNthNodeFromEndOfList obj = new RemoveNthNodeFromEndOfList();
    		
    		ListNode original1 = SinglyLinkedList.ints2List(1, 2, 3, 4, 5);
    		ListNode expected1 = SinglyLinkedList.ints2List(1, 2, 3, 5);
    		assertTrue(SinglyLinkedList.areTwoListEqual(expected1, obj.removeNthFromEnd2(original1, 2)));
    		
    		ListNode original2 = new ListNode(1);
    		assertNull(obj.removeNthFromEnd2(original2, 1));
    		
    		ListNode original3 = SinglyLinkedList.ints2List(1, 2);
    		ListNode expected3 = new ListNode(1);
    		assertTrue(SinglyLinkedList.areTwoListEqual(expected3, obj.removeNthFromEnd2(original3, 1)));
    	}
    }

[https_leetcode.com_problems_remove-nth-node-from-end-of-list]: https://leetcode.com/problems/remove-nth-node-from-end-of-list/