Algorithm: List Related Problems
Data Structure: List
List is a data structure which made up of several node, each node has a pointer to its next node or previous node.
Usually we use the first node of list to represent the list.
// definition of node
public class Node {
int val;
Node next;
}
Let dive into some classic list-related problem
Find the middle node of list
The tricky part here is when the count of nodes in list is even, should we find the upper middle one or lower middle one?
public class FindMiddleNode {
// in this way, when #nodes in list is even, then find the upper middle point
// if #nodes is odd, then find the middle node
public Node findMiddle(Node head) {
Node fast = head, slow = head;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
}
}
Clone list
There are several ways to clone the list
public class CloneList {
public Node clone(Node head) {
Node cur = head;
Node copyHead = new Node(head.val);
Node copyCur = copyHead;
while(cur.next != null) {
copyCur.next = new node(cur.next.val);
cur = cur.next;
copyCur = copyCur.next;
}
return copyHead;
}
}
Make the List as Netherland Flag
use 6 pointers to split smaller area, equal area and bigger area.
public class NetherLandFlagList {
public Node process(Node head, int val){
Node smallerHead = null, smallerTail = null, equalHead = null, equalTail = null, biggerHead = null, biggerTail = null;
while(head != null) {
if (head.val < val) {
if (smallerHead == null) {
smallerHead = head;
smallerTail = head;
} else {
smallerTail.next = head;
smallerTail = head;
}
} else if (head.val == val) {
if (equalHead == null) {
equalHead = head;
equalTail = head;
} else {
equalTail.next = head;
equalTail = head;
}
} else {
if (biggerHead == null) {
biggerHead = head;
biggerTail = head;
} else {
biggerTail.next = head;
biggerTail = head;
}
}
head = head.next;
}
// connect 3 areas
if (smallerTail != null) {
smallerTail.next = equalHead != null ? equalHead : biggerHead;
}
if (equalTail != null) {
equalTail.next = biggerHead;
}
// find valid head
if (smallerHead != null) {
return smallerHead;
} else if (equalHead != null) {
return equalHead;
} else {
return biggerHead;
}
}
}
Determine if a list is palindrome
I will provide two solutions here, one is leveraging extra data structure and one is not
public class PalindromeListDetector1 {
// leverage another data structure: Stack
public boolean isPalindromeList(Node head) {
// find the middle or upper middle of list
Node fast = head, slow = head;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// put the second part of list into stack
Stack<Node> stack = new Stack();
slow = slow.next;
while(slow != null) {
stack.push(slow);
slow = slow.next;
}
Node left = head;
while(!stack.isEmpty()) {
if (left.val != (stack.pop()).val) {
return false;
}
left = left.next;
}
return true;
}
public boolean isPalindromeList(Node head) {
// 1. find the middle node of list
// 2. reverse the second half of list
// 3. compare first half with second half
// 4. recover the reversed 2nd half
Node middle = findMiddleNode(head);
Node tail = reverseList(middle);
Node newTail = tail;
while(tail != null) {
if (tail.val != head.val) {
return false;
}
tail = tail.next;
head = head.next;
}
tail = reverseList(newTail);
middle.next = tail;
}
// for list with even nodes, return the upper middle node
// for list with odd nodes, return the middle node
private Node findMiddleNode(Node head) {
Node fast = head, slow = head;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
// reverse the list, return new head
private Node reverseList(Node head) {
Node prev = null, next = null;
while(head.next != null) {
next = head.next;
head.next = prev;
prev = head;
head = next;
}
head.next = prev;
return head;
}
}
Find the intersect of two list
public class FindListsIntersect {
public Node findIntersectStartNode(Node a, Node b) {
// 1. check if there is any loop in list
// 2. check if two list whether has intersect or not
// 3. handling when two lists don't have loop
// 4. handling two lists have loop
boolean isAHasLoop = isListHasLoop(a);
boolean isBHasLoop = isListHasLoop(b);
if (isAHasLoop != isBHasLoop) {
// only one list has loop
return null;
}
if (!isAHasLoop) {
// both lists don't have loop
return findIntersectForNonLoopList(a, b, null);
} else {
return findIntersectForLoopList(a, b);
}
}
private boolean isListHasLoop(Node node) {
Set<Node> set = new HashSet<>();
while(node != null) {
if (set.contains(node)) {
return true;
}
set.add(node);
node = node.next;
}
return false;
}
private Node findIntersectForNonLoopList(Node a, Node b, Node end) {
int aLength = 1, bLength = 1;
Node aTail = a, bTail = b;
while(aTail.next != end) {
aTail = aTail.next;
aLength++;
}
while(bTail.next != end) {
bTail = bTail.next;
bLength++;
}
if(aTail != bTail) {
return null;
}
Node longerHead = aLength > bLength ? a : b;
Node shorterHead = longerHead == a ? b : a;
int distance = Math.abs(aLength - bLength);
while(distance != 0) {
longerHead = longerHead.next;
distance--;
}
while(longerHead != shorterHead) {
longerHead = longerHead.next;
shorterHead = shorterHead.next;
}
return longerHead;
}
private Node findIntersectForLoopList(Node a, Node b) {
Node aLoopStart = findLoopStart(a);
Node bLoopStart = findLoopStart(b);
if (aLoopStart == bLoopStart) {
// when the intersect is outside loop
return findIntersectForNonLoopList(a, b, aLoopStart.next);
} else {
// when the intersect is inside loop
return aLoopStart;
}
}
private Node findLoopStart(Node head) {
Set<Node> set = new HashSet<>();
while(!set.contains(head)) {
set.add(head);
head = head.next;
}
return head;
}
// another way to find loop start, without using HashSet
private Node findLoopStart1(Node head) {
Node fast = head, slow = head;
while(fast != slow) {
fast = fast.next.next;
slow = slow.next;
}
fast = head;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}