LeetCode - Easy - 237. Delete Node in a Linked List

你的名字 2022-12-30 14:55 115阅读 0赞

## Topic ##

*  Linked List

## Description ##

[https://leetcode.com/problems/delete-node-in-a-linked-list/][https_leetcode.com_problems_delete-node-in-a-linked-list]

Write a function to **delete a node** in a singly-linked list. You will **not** be given access to the head of the list, instead you will be given access to **the node to be deleted** directly.

It is **guaranteed** that the node to be deleted is **not a tail node** in the list.

**Example 1**:

Input: head = [4,5,1,9], node = 5
    Output: [4,1,9]
    Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

**Example 2**:

Input: head = [4,5,1,9], node = 1
    Output: [4,5,9]
    Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

**Example 3**:

Input: head = [1,2,3,4], node = 3
    Output: [1,2,4]

**Example 4**:

Input: head = [0,1], node = 0
    Output: [1]

**Example 5**:

Input: head = [-3,5,-99], node = -3
    Output: [5,-99]

**Constraints**:

*  The number of the nodes in the given list is in the range \[2, 1000\].
 *  \-1000 <= Node.val <= 1000
 *  The value of each node in the list is **unique**.
 *  The node to be deleted is **in the list** and is **not a tail** node

## Analysis ##

方法一：类似数组的元素删除算法。

方法二：下节点的值覆盖当前节点值，然后删除下一节点。

## Submission ##

import com.lun.util.SinglyLinkedList.ListNode;
    
    public class DeleteNodeInALinkedList { 
    
    	// 方法一：
    	public void deleteNode1(ListNode node) { 
    		ListNode p1 = node, p2 = node.next;
    
    		while (p2 != null) { 
    			p1.val = p2.val;
    
    			if (p2.next == null)
    				p1.next = null;// help GC
    
    			p1 = p2;
    			p2 = p2.next;
    		}
    	}
    
    	// 方法二：
    	public void deleteNode2(ListNode node) { 
    		node.val = node.next.val;
    		ListNode p = node.next;
    		node.next = p.next;
    		p = null;// help GC
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.SinglyLinkedList;
    import com.lun.util.SinglyLinkedList.ListNode;
    
    public class DeleteNodeInALinkedListTest { 
    
    	@Test
    	public void test1() { 
    		DeleteNodeInALinkedList obj = new DeleteNodeInALinkedList();
    		
    		ListNode node1 = new ListNode(4),
    				node2 = new ListNode(5),
    				node3 = new ListNode(1),
    				node4 = new ListNode(9);
    		
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		
    		obj.deleteNode1(node2);
    		assertEquals("4 -> 1 -> 9", SinglyLinkedList.print(node1));
    	}
    	
    	@Test
    	public void test1_2() { 
    		DeleteNodeInALinkedList obj = new DeleteNodeInALinkedList();
    		
    		ListNode node1 = new ListNode(4),
    				node2 = new ListNode(5),
    				node3 = new ListNode(1),
    				node4 = new ListNode(9);
    		
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		
    		obj.deleteNode2(node2);
    		assertEquals("4 -> 1 -> 9", SinglyLinkedList.print(node1));
    	}
    
    	@Test
    	public void test2() { 
    		DeleteNodeInALinkedList obj = new DeleteNodeInALinkedList();
    
    		ListNode node1 = new ListNode(4),
    				node2 = new ListNode(5),
    				node3 = new ListNode(1),
    				node4 = new ListNode(9);
    		
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		
    		obj.deleteNode1(node3);
    		
    		assertEquals("4 -> 5 -> 9", SinglyLinkedList.print(node1));
    		
    	}
    	
    	@Test
    	public void test2_2() { 
    		DeleteNodeInALinkedList obj = new DeleteNodeInALinkedList();
    		
    		ListNode node1 = new ListNode(4),
    				node2 = new ListNode(5),
    				node3 = new ListNode(1),
    				node4 = new ListNode(9);
    		
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		
    		obj.deleteNode2(node3);
    		
    		assertEquals("4 -> 5 -> 9", SinglyLinkedList.print(node1));
    	}
    	
    	@Test
    	public void test3() { 
    		DeleteNodeInALinkedList obj = new DeleteNodeInALinkedList();
    		
    		ListNode node1 = new ListNode(1),
    				node2 = new ListNode(2),
    				node3 = new ListNode(3),
    				node4 = new ListNode(4);
    		
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		
    		obj.deleteNode1(node3);
    		
    		assertEquals("1 -> 2 -> 4", SinglyLinkedList.print(node1));
    		
    	}
    	
    	@Test
    	public void test4() { 
    		DeleteNodeInALinkedList obj = new DeleteNodeInALinkedList();
    		
    		ListNode node1 = new ListNode(0),
    				node2 = new ListNode(1);
    		
    		node1.next = node2;
    		
    		obj.deleteNode1(node1);
    		
    		assertEquals("1", SinglyLinkedList.print(node1));
    		
    	}
    	
    	@Test
    	public void test5() { 
    		DeleteNodeInALinkedList obj = new DeleteNodeInALinkedList();
    		
    		ListNode node1 = new ListNode(-3),
    				node2 = new ListNode(5),
    				node3 = new ListNode(-99);
    		
    		node1.next = node2;
    		node2.next = node3;
    		
    		obj.deleteNode1(node1);
    		
    		assertEquals("5 -> -99", SinglyLinkedList.print(node1));
    		
    	}
    }

[https_leetcode.com_problems_delete-node-in-a-linked-list]: https://leetcode.com/problems/delete-node-in-a-linked-list/