链表的节点删除
在删除链表的节点步骤如下:
1. 找到被删除节点的前面一个节点
2. 将前面节点的 next 节点改成下一个节点
3. 将被删除节点的内存释放
- public class deleteNode
- {
- Node head;
- class Node
- {
- int data;
- Node next;
- Node(int d)
- {
- data = d;
- next = null;
- }
- }
- void deleteNode(int key)
- {
- // Store head node
- Node temp = head, prev = null;
- // If head node itself holds the key to be deleted
- if (temp != null && temp.data == key)
- {
- head = temp.next; // Changed head
- return;
- }
- // Search for the key to be deleted, keep track of the
- // previous node as we need to change temp.next
- while (temp != null && temp.data != key)
- {
- prev = temp;
- temp = temp.next;
- }
- // If key was not present in linked list
- if (temp == null) return;
- // Unlink the node from linked list
- prev.next = temp.next;
- }
- public void push(int new_data)
- {
- Node new_node = new Node(new_data);
- new_node.next = head;
- head = new_node;
- }
- public void printList()
- {
- Node tnode = head;
- while (tnode!=null)
- {
- System.out.println(tnode.data);
- tnode = tnode.next;
- }
- }
- public static void main(String[] args)
- {
- deleteNode llist = new deleteNode();
- llist.push(7);
- llist.push(1);
- llist.push(3);
- llist.push(2);
- System.out.println("\nCreated Linked list is:");
- llist.printList();
- llist.deleteNode(1); // Delete node at position 4
- System.out.println("\nLinked List after Deletion at position 4:");
- llist.printList();
- }
- }
接下来我们来考虑一道 leetcode 题:
- 237. Delete Node in a Linked List
- Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
- Given linked list -- head = [4,5,1,9], which looks like following:
- 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.
- class Solution {
- public void deleteNode(ListNode node) {
- node.val = node.next.val;
- node.next = node.next.next;
- }
- }
在这一题中, 没有传入当前节点的上一个节点. 由于上一个节点知道下一个节点就是当前节点. 因此只要我们将当前节点的所有信息替换成当前节点的下一个节点的信息, 我们也就变相完成了节点的删除.
- References:
- deletion linked list
来源: http://www.bubuko.com/infodetail-3354523.html