Singly Linked List
A typical singly linked list is chain of ListNode which has two members, int val for data field, ListNode next for next reference point. For my own convenience, if I don't specify the type of linked list, it means it is a singly linked list in article.
Be ware of, I didn't apply any generic to the example class ListNode. Just use Leetcode's definition. Leetcode doesn't apply any C# naming conventions. E.g. C# should use camelCasing for method arguments and local variables, PascalCasing for class names and methods name.
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
Initialize, Traversal, Length
A linked list must have a head.Traversal start from here, move by using next point, till the end.
Not like array is allocate and initialize with fixed length, linked list calculate length by traversal all the nodes, and it could be change if linked list add/remove nodes. To avoid re-calculate every time, we could use a private field variable to store the count and keep it update while add/remove nodes.
public ListNode Initialize(int[] arr)
{
var dummy = new ListNode(0);
var node = dummy;
for(var i=0;i<arr.Length;i++)
{
node.next = new ListNode(arr[i]);
node = node.next;
}
return dummy.next;
}
public int GetLength(ListNode head)
{
var node = head; // we use node to traversal the lined list
var count = 0;
while(node !=null) { node = node.next; count++;}
return count;
}
public ListNode GetTail(ListNode head)
{
var node = head;
while(node!=null && node.next!=null) node = node.next;
// after while loop, we either get a tail node or null if tail doesn't exist(head is null)
return node;
}
We use a dummy node to help create the linked list. If we don't use dummy node, then we need to initialize the head with real value. Before we could do that, we need to check if head is null. that will make code a little bit more complex.
Be careful below approach is wrong!
public ListNode Initialize(int[] arr)
{
ListNode head = null; //head doesn't have allocate any memory, null means no reference.
var node = head; //node has no reference
for(var i=0;i<arr.Length;i++)
{
node = new ListNode(arr[i]); // node was initialized and have a reference, but it won't apply to head
node = node.next; // node has been assign to null again.
}
// after loop, head, node are still null with none reference
return head;
}
Get, Update, Replace, Remove
public ListNode GetByIndex(ListNode head, int index)
{
if(head==null||index<0) return null;
// index is zero based, from 0...
var node = head;
while(index-->0 && node!=null){
node = node.next;
}
// return null if index >= length;
return node;
}
public void Update(ListNode head, int index, int val)
{
var node = GetByIndex(head, index);
if(node!=null) node.val = val;
}
public void Replace(ListNode head, int index, ListNode n2)
{
if(head==null||index<0) return;
if(index==0) {
if(n2 == null) return; // invalid operation, even we assign null to head, it worn't change original head
head.val = n2.val;
head.next = n2.next;
return;
}
var pre = GetByIndex(index-1);
pre.next = n2; // all nodes in previous linked list after pre, will be abandoned.
}
Find middle node
use two points, slow and fast, slow move 1 step each time, fast move 2 step each time. when fast or fast.next reach the end.
slow one is the middle node if total nodes is odd or middle (right based) node if total nodes is even
Swap, Reverse
Swap
The easy way to swap this just swap the value. It become more complex if you were asked to swap the nodes.
There are some critical case need to be considered. E.g
one of node is head, this make impossible to swap node in-place if you head parameter doesn't have a by ref keyword. You cannot just head = newHead to change the head's reference in caller by default.
node1.next == node2. need to be treated in another way. Once you finish the common case, draw a test case linked list, go through case like 10->9->8->7->null swap 10, 9 then you will understand.
// just swap the val, no need to use head to locate node
public void Swap(ListNode n1, ListNode n2)
{
if(n1==null||n2==null) return;
var t = n1.val;
n1.val = n2.val;
n2.val = t;
}
// do actual swap the node, need to use head to locate the node
public ListNode Swap(ListNode head, ListNode n1, ListNode n2)
{
if (n1 == null || n2 == null || n1 == n2) return head;
if (n2.next == n1) return Swap(head, n2, n1);
var dummy = new ListNode(0);
dummy.next = head;
var pre1 = GetPrevious(head, n1) ?? dummy;
var pre2 = GetPrevious(head, n2) ?? dummy;
var next = n2.next;
if(n1.next == n2) // handle 10->8->6->5 swap 10, 8 node
{
pre1.next = n2;
// n2.next = n1.next; this just create a cycle, don't do this
n2.next = n1;
//pre2.next = n1; this just create another cycle, don't do this
n1.next = next; //n2.next;
}
else
{
pre1.next = n2;
n2.next = n1.next;
pre2.next = n1;
n1.next = next; //n2.next;
}
return dummy.next;
}
public ListNode GetPrevious(ListNode head, ListNode node)
{
if(head == node) return null;
var n = head;
while(n!=null)
{
if(n.next==node) return n;
n = n.next;
}
return null;
}
Reverse
There are lots of linked list require temporary variable to store intermediate node reference. It is quite hard to remember which node's which state should be remember.
You can see in all example by now, we use a next point to remember last node's next. In swap case next = n2.next.
[Tips] when you want to manipulate linked list, and need to temporary store node or node.next point, if there are multiple candidate, just choose the last node.next. Start thinking to manipulate last node, till you operations are all done.
public ListNode ReverseList(ListNode head) {
if(head==null) return head;
var dummy = new ListNode(0);
dummy.next = head;
var tail = head;
var cur = head.next;
while(cur!=null){
var next = cur.next;
cur.next = dummy.next;
dummy.next = cur;
tail.next = next;
cur = next;
Console.WriteLine(cur==null?0: cur.val);
}
return dummy.next;
}
- we need dummy point, so we could process head easy
- tail will always point to the head. and it is tail of reversed linked list
- cur is initialized to head.next we will iterate from there to end, move it to head
- don't forget to set tail.next otherwise, there will be a cycler linked list generated at the end of reversed linked list
Below is Java code copy from leetcode with both iterative and recursive way, really smart.
public ListNode reverseList(ListNode head) {
/* iterative solution */
ListNode newHead = null;
while (head != null) {
ListNode next = head.next; // keep next point
head.next = newHead; // before move newHead and head, we need to remove head.next,
// and reverse point to pre which is newHead.
newHead = head; // newHead is always previous of head, till head is null
head = next; // head will iterate from head to null
}
return newHead;
}
public ListNode reverseList(ListNode head) {
/* recursive solution */
return reverseListInt(head, null);
}
private ListNode reverseListInt(ListNode cur, ListNode pre) {
if (cur== null)
return pre; // last node's previous is new head at the end of recusion
ListNode next = cur.next;
cur.next = pre;
return reverseListInt(next, cur); // head either null or previous node of new header
}
Intersection of two linked list
Claim:
Use two points a,b to iterate two linked list, if reach the end of one, then reset the end point to another one. If they have intersection, the firs node a==b, is the intersection node.
Proof:
List1 = ListA+ListC
List2 = ListB+ListC
with above algo,
Iteration of node2 -> ListA + ListC + List B + ListC
Iteration of node1 -> List B + ListC + ListA + ListC
you can see, they will meet at first node of second ListC.
public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null) return null;
var n1 = headA;
var n2 = headB;
while(n1 != n2){
if(n1 == n2) break;
n1 = n1!=null? n1.next : headB;
n2 = n2!=null? n2.next : headA;
}
return n1;
}
}
Palindrome Linked List
Iterative solution use two points algorithm. Recursive solution is mart.
public bool IsPalindromeRecursive(ListNode head)
{
return head == null || recurse(head, head) != null;
}
private ListNode recurse(ListNode node, ListNode head)
{
if (node == null) return head; // exit recusion when reach end of tail
ListNode res = recurse(node.next, head); // in recusion, node iterate from tail to head,
// res from head to tail.
if (res == null) return res;
else if (res.val == node.val) return (res.next == null ? res : res.next); // return compare node(cur from tail) to head
else return null;
}
Copy List with Random Pointer
- Solution1 is using Dictionary<Original, Copy> , Copy.Random = Map[Original.Random]
- Solution2 is connect Original and Copy, use Copy.Random = Original.Random.Next;
Merge k Sorted Lists
Add all list nodes into a PriorityQueue
BFS pq, add smallest node to result, if node has next, move to next, and add it to queue
loop till no more node in pq.