237. Delete node in a linked list

Difficulty: 

Frequency: 

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.


 

My solution:
Data structure:
list
Steps:
1. Copy the next node to current node
2. Delete next node
Complexity:
Runtime: O(1)
Space: O(n)
Test cases:
Corner cases:
Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode *temp = node->next;
        *node = *node->next;
        delete temp;
        temp = NULL;
    }
};



Things to learn:
1. Remember to free the data
 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s