700622. Deletion and Reverse in Circular Linked List
Deletion and Reverse in Circular Linked List
Summary
In this problem, we are given a circular linked list and our task is to delete a node from the list while maintaining the circular property. Additionally, we need to reverse the remaining nodes in the list. This problem involves understanding of circular linked lists and their manipulation.
Detailed Explanation
To solve this problem, we will follow these steps:
-
Delete Node: First, we need to find the node that needs to be deleted. If the given node is the last node in the circular list (i.e., its next pointer points to the first node), then we need to update the next pointer of the previous node to point to the node after the current node.
-
Reverse Nodes: After deleting the node, we need to reverse the remaining nodes in the list. To do this, we will initialize three pointers: prev, curr, and next. Initially, set prev to null, curr to the head of the list (which is the second node), and next to curr's next.
-
Reverse: Then, traverse the list by updating prev to curr, curr to next, and next to next's next until we reach the end of the list (i.e., when next becomes null). At this point, prev points to the new head of the reversed list.
-
Update Head: Finally, update the head of the list to be prev.
Time Complexity: O(n), where n is the number of nodes in the circular linked list. Space Complexity: O(1) as we are not using any extra space that scales with the input size.
Optimized Solutions
Java
public class Solution {
public void deleteAndReverse(Node head, int key) {
Node curr = head;
if (curr == null || curr.next == null) return; // empty list or only one node
while (curr.next != head && curr.next.val != key) {
curr = curr.next;
}
if (curr.next == head) {
if (head.val == key) {
Node newHead = head.next;
curr.next = newHead;
return;
} else {
return; // node not found
}
}
Node prev = null;
Node next = curr.next;
while (next != head) {
Node temp = next;
next = next.next;
temp.next = prev;
prev = temp;
}
if (head.val == key) {
curr.next = prev;
} else {
return; // node not found
}
}
}