It really waste me too much time and energy to understand the last two linked list problems.
Question No.1 is copy random list
public Node copyRandomList(Node head) {
if (head == null) return head;
Node ptr = head;
// step1: copy each node and put it right next to the origin node
while (ptr != null) {
Node newNode = new Node(ptr.val);
newNode.next = ptr;
ptr.next = newNode;
ptr = ptr.next;
}
// step2: generate the random nodes of new nodes
ptr = head;
while (ptr != null) {
ptr.next.random = (ptr.random != null) ? ptr.random.next : null;
ptr = ptr.next.next;
}
// step3: release the link between origin linked list and new list
ListNode old_list = head;
ListNode new_list = head.next;
ListNode new_head = head.next;
while (old_list != null) {
old_list.next = old_list.next.next;
new_list.next = (new_list.next != null) ? new_list.next.next : null;
old_list = old_list.next;
new_list = new_list.next;
}
return new_head;
}This problem is really tricky, and it use so many lines of code to solve. But at the same time it's quite intuitive if you draw the relations of new list and old list on the paper or just in your head.
And the O(1) space answer is not easy to come up with if you haven't solved many linked list problems.
Last but not least, until now I can't understand the iteration solving method, I even don't have enough patient to read through that method :(
Question No.2 is the rotation of linked list
public Node rotateRightList(Node head, int k) {
if (head == null) return head;
if (head.next == null) return head;
// step1: iterate the list through and loop the origin list with linking the tail to the head
// btw, count the nums of list
Node old_tail = head;
int n;
for (n = 1; old_tail.next != null; n++) {
old_tail = old_tail.next;
}
old_tail.next = head;
// step2: get the brand new tail and cut the loop generated in step1
Node new_tail = head;
for (int i = 0; i < n - k % n - 1; i++) {
new_tail = new_tail.next;
}
Node new_head = new_tail.next;
new_tail.next = null;
return new_head;
}It's really tricky that why to iterate till n - k % n - 1, even now I can't explain it but just know how to write code such way.
The rest part is easy to understand, but the key of this problem is to calculate the new head's position and concern the situation of k > n.