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 = 5Output: [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 = 1Output: [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.
Note:
- The linked list will have at least two elements.
- All of the nodes? values will be unique.
- The given node will not be the tail and it will always be a valid node of the linked list.
- Do not return anything from your function.
This is a leetcode question: https://leetcode.com/problems/delete-node-in-a-linked-list/
Solution:
Time Complexity: O(n)
Space Complexity: O(1)
This is a very simple linked list problem .
First we need to check if the node which is to be deleted is the last node. if it is last node than we can simple assign it null.
If it is a node in middle than we can assign the value of next node to this node. After that we can set the next of this node to next of next node(i know this is bit confusing so the Java implementation below will make this clear.)
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public void deleteNode(ListNode node) { if(node.next == null){ node = null; } node.val = node.next.val; node.next = node.next.next; }}
