Reversing Linked List

Swap nodes in pairs

use dummy node to deal with edge case where the problem involves the operation of the head of the linked list. And we need to use two pointers like pre and cur to implement the swap operation along the way.

public ListNode swapPairs(ListNode head) {
    // dummy
    // cur, cur.next
    // cur != null && cur.next != null, swap two nodes in between, 
    ListNode dummy = new ListNode(-1);
    dummy.next = head;

    ListNode pre = dummy, cur = head;
    while (cur != null && cur.next != null) {
        ListNode next = cur.next.next, first = cur, second = cur.next;

        first.next = next;
        second.next = first;
        pre.next = second;

        pre = first;
        cur = next;
    }

    return dummy.next;
}

Reverse Linked List

this is kind of a technique that we should remember.

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode temp = head.next;
        head.next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

Reverse Linked List 2

a little bit complex than reverse linked list 1, and we should calculate the steps that cur pointer move carefully.

Before looking at the algorithm, it's important to understand how the link reversal will work and what set of pointers will be required for the same. Let's say we have a linked list consisting of three different nodes,A → B → Cand we want to reverse the links between the nodes and obtainA ← B ← C.

Suppose we have at our disposal, two pointers. One of them points to the nodeAand the other one points to the nodeB. Let's call these pointersprevandcurrespectively. We can simply use these two pointers to reverse the link betweenA and

B.cur.next = prev

The only problem with this is, we don't have a way of progressing further i.e. once we do this, we can't reach the nodeC. That's why we need a third pointer that will help us continue the link reversal process. So, we do the following instead.

third = cur.next
cur.next = prev
prev = cur
cur = third

1. We need two pointers,prevandcuras explained above.

2. Theprevpointer should be initialized toNoneinitially whilecuris initialized to theheadof the linked list.

3. We progress thecurpointer one step at a time and theprevpointer follows it.

4. We keep progressing the two pointers in this way until thecurpointer reaches the m^{th}mthnode from the beginning of the list. This is the point from where we start reversing our linked list.

5. An important thing to note here is the usage of two additional pointers which we will call astailandcon. Thetailpointer points to them^{th}mthnode from the beginning of the linked list and we call it a_tail_pointer since this node becomes the tail of the reverse sublist. Theconpoints to the node one beforem^{th}mthnode and this connects to the new head of the reversed sublist. Let's take a look at a figure to understand these two pointers better.

6. Thetailand theconpointers are set once initially and then used in the end to finish the linked list reversal.

7. Once we reach them^{th}mthnode, we iteratively reverse the links as explained before using the two pointers. We keep on doing this until we are done reversing the link (next pointer) for then^{th}nthnode. At that point, theprevpointer would point to then^{th}nthnode

8. We use theconpointer to attach to theprevpointer since the node now pointed to by theprevpointer (then^{th}nthnode from the beginning) will come in place of them^{th}mthnode due after the reversal. Similarly, we will make use of thetailpointer to connect to the node next to theprevnode i.e.(n+1)^{th}(n+1)thnode from the beginning.

We do the above_iteratively_and we will achieve what the question asks us to do. Let's look at the steps for the algorithm now.

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null) return head;

        int i = 1;
        ListNode prev = null, cur = head;
        while (i < m) {
            prev = cur;
            cur = cur.next;
            i++;
        }

        ListNode before = prev, tail = cur; // before can be null, to be used later 
        for (; i <= n; ++i) {    // the key point is do one more time, cur points to the next un-reversed node.
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        if (before != null) {
            before.next = prev;
        } else {
            head = prev;
        }
        tail.next = cur;

        return head;
    }
}

How to do it using recursive way?

Rotate Linked List

The idea is that, first round we need to do is to calculate the length of the list. and then do the module operation based on that in order to avoid repetitive rotation.

Then we actually split the original list into two separate lists. So in order to accomplish the rotation process, we need to get several list nodes like the end of the first sublist, the head of the second sublist, and the end of the second sublist.

Finally, we finish rotate process by modify those list node relationship.

public static ListNode rotateRight(ListNode head, int k) {
    if (head == null) return head;

    ListNode cur = head;
    int i = 0;
    while (cur != null) {
        cur = cur.next;
        i++;
    }

    int offset = k % i;
    if (offset == 0) {
        return head;
    }

    cur = head;
    int j = 0;
    while (j < (i - offset - 1)) {
        cur = cur.next;
        j++;
    }
    ListNode newTail = cur;
    ListNode newHead = cur.next;
    ListNode tail = newHead;
    while(tail.next != null) {
        tail = tail.next;
    }

    tail.next = head;
    newTail.next = null;

    return newHead;
}

Reorder list

In general, there are three steps, get the middle node in the list, reverse the latter part of the list, and merge the two list interleavingly. Time complexity is O(n), and space complexity is O(1).

Note that, if you want to get the middle node, fast and slow pointer is enough, but when need to merge two pointers, you need pre pointer.

    public static void reorderList(ListNode head) {
        if (head == null) return;

        // get the middle node in the list
        // get the middle node, just fast and slow pointer enough,
        // but if you want to merge two pointers, you need pre pointer.
        ListNode fast = head, slow = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        if (pre == null) return;
        pre.next = null;

        // reverse the latter part of the list
        ListNode newAfterHead = reverseList(slow);

        // merge two list alternatively
        mergeTwoListAlternative(head, newAfterHead);
    }

    private static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    private static void mergeTwoListAlternative(ListNode l1, ListNode l2) {
        ListNode before = l1, after = l2;
        ListNode dummy = new ListNode(-1);
        dummy.next = l1;
        ListNode cur = dummy;
        boolean odd = false;
        while (before != null && after != null) {
            if (odd) {
                cur.next = after;
                after = after.next;
            } else {
                cur.next = before;
                before = before.next;
            }
            odd = !odd;
            cur = cur.next;
        }

        if (before != null) {
            cur.next = before;
        }
        if (after != null) {
            cur.next = after;
        }
    }