Hello everyone. Today we will analyse popular tasks for linked lists.
Also you can check Linked List Tips.
The first task on our list is Merge Two Sorted Lists.
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
How do we approach this problem? One of the most popular techniques for working with linked lists is two-pointers. In our case, we can use the beginning of each of the lists as pointers and move the elements only if one is larger than the other. Also, do not forget to supplement our resulting list with the remaining elements of the list that is longer.
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode empty = new ListNode();
ListNode emptyHead = empty;
while(list1 != null && list2 != null) {
if(list1.val > list2.val) {
empty.next = list2;
list2 = list2.next;
empty = empty.next;
} else {
empty.next = list1;
list1 = list1.next;
empty = empty.next;
}
}
while (list1 != null) {
empty.next = list1;
list1 = list1.next;
empty = empty.next;
}
while (list2 != null) {
empty.next = list2;
list2 = list2.next;
empty = empty.next;
}
return emptyHead.next;
}
Next, we will smoothly move on to the **Add Two Numbers **task.
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
In our case, we need to add numbers. But there may be a situation when the amount will be more than 10. Then it is worth transferring the balance to the next operation. There is also a case when the sum is 10. Then you can take it out in a separate case or combine it with a condition greater than 10.
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode rezNodeHead = new ListNode();
ListNode rezNode = rezNodeHead;
int rest = 0;
while (l1 != null || l2 != null) {
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int rez = rest + val1 + val2;
ListNode tmp = new ListNode();
if (rez == 10) {
tmp.val = 0;
rezNode.next = tmp;
rezNode = tmp;
rest = 1;
} else if (rez > 10) {
int val = rez % 10;
rest = rez / 10;
tmp.val = val;
rezNode.next = tmp;
rezNode = tmp;
} else {
tmp.val = rez;
rezNode.next = tmp;
rezNode = tmp;
rest = 0;
}
l1 = (l1 != null) ? l1.next : null;
l2 = (l2 != null) ? l2.next : null;
}
if (rest != 0) {
ListNode tmp = new ListNode();
tmp.val = rest;
rezNode.next = tmp;
}
return rezNodeHead.next;
}
_ If you have any questions about this problem, I will be happy to answer._
There is no way around Flatten a Multilevel Doubly Linked List. In this task, a node can have a child node.
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.
Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.
Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.
There are several interesting approaches to solving this problem. I will analyse the easiest (for me) to write. It doesn't take long to write this approach. My idea is that we are running through the nodes. When the node has a child, we rearrange the link so that the list with the child sodas fits into our current list. There is a nuance that we will have to run through the child node two times in the worst case.
public static Node flatten(Node head) {
Node headTmp = head;
if (head == null) {
return head;
}
while (head != null) {
Node child = head.child;
Node next = head.next;
if (child != null) {
head.next = child;
while (child.next != null) {
child = child.next;
}
child.next = next;
next.prev = child;
}
head.child = null;
head = head.next;
}
return headTmp;
}
How can this algorithm be improved? When meeting a child node, it is possible to recursively into the depths of the list. We will embed it in the parent when we get to the most profound child element. Visually, it will look completely different from the previous algorithm.
If you have any questions, I will be happy to answer them.
Do not forget about the rather popular **Odd-Even Linked List **task.
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.
You can remember the technique of the two runners. We can prepare two nodes for odd and even elements, and we will successfully add them. In the end, we need to merge two lists. How to do it? For this, we need a tail. Therefore, when filling underneath, we will shift a tail. And at the end, we combine tail odd and head even.
public ListNode oddEvenList(ListNode head) {
if (head == null){
return head;
}
ListNode oddHead = null;
ListNode oddTail = null;
ListNode evenHead = null;
ListNode evenTail = null;
int counter = 0;
while(head != null) {
counter += 1;
if (counter % 2 != 0) {
if (oddHead == null) {
oddHead = head;
oddTail = head;
} else {
oddTail.next = head;
oddTail = head;
}
} else {
if (evenHead == null) {
evenHead = head;
evenTail = head;
} else {
evenTail.next = head;
evenTail = head;
}
}
head = head.next;
}
oddTail.next = evenHead;
if (evenTail != null){
evenTail.next = null;
}
return oddHead;
}
Oldest comments (0)