Write a Program to Move the last element to Front in a Linked List

The problem, simply

You get a singly linked list. Unhook the last box and put it at the front, so it becomes the new head. Everything else keeps its order. Give back the new head.

For example 1 2 3 4 5 becomes 5 1 2 3 4. Move the box itself; do not just copy numbers around.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count first, then walk to the second to last box.

1. Walk the chain and count the boxes, n.
2. Walk n - 2 steps from the head. You are on the second to last box.
3. Take its next (the last box), set the second to last box's next to null, point the last box at the old head, and return it.

class Solution {
    public ListNode moveToFront(ListNode head) {
        if (head == null || head.next == null) return head;
        int n = 0;
        for (ListNode t = head; t != null; t = t.next) n++;   // count the boxes
        ListNode curr = head;
        for (int i = 0; i < n - 2; i++) curr = curr.next;     // second to last box
        ListNode last = curr.next;
        curr.next = null;      // new end of the chain
        last.next = head;      // last box goes in front
        return last;
    }
}

How long it takes: one walk to count and almost one more to find the box, O(n). Extra room: O(1).

Way 2: the clever way

Do it in one walk with two fingers one box apart. last walks to the end, and secondLast always trails one box behind it.

1. If the chain has 0 or 1 boxes, return it.
2. Start with secondLast = null and last = head. While last.next is not null, move secondLast to last and last forward.
3. Change three arrows: secondLast.next = null, last.next = head, and the head becomes last.

class Solution {
    public ListNode moveToFront(ListNode head) {
        if (head == null || head.next == null) return head;   // 0 or 1 box
        ListNode secondLast = null, last = head;
        while (last.next != null) {        // walk to the end, one box apart
            secondLast = last;
            last = last.next;
        }
        secondLast.next = null;            // the old second to last is the new end
        last.next = head;                  // the old last box leads now
        return last;
    }
}

How long it takes: one walk, O(n). Extra room: two fingers, O(1). You cannot do better than O(n) on a singly list, because the only way to reach the last box is to walk there.

Watch out for

• Check head.next == null first. With one box, secondLast stays null and secondLast.next would crash.
• Return the new head. The caller's old head variable still points to box 1, which is now second.
• Shifting the numbers instead (copy each number one box to the right and write the last number into the head) prints the same answer, but the boxes did not move. If a box carries more than a number, that is wrong.

What interviewers ask next

• Move the first box to the end instead? Walk to the last box, set last.next = head, move the head to head.next, and set the old head's next to null.
• Move the last k boxes to the front? That is rotating right by k (LeetCode 61). Use the two finger gap from "nth node from the end" to find the box before the last k, cut there, and hook the old tail to the old head.
• What if the list is doubly linked or keeps a tail pointer? Then the last box is known right away and the move is O(1): tail.prev becomes the new tail.
• Do it with recursion? Recurse to the second to last box and do the same three changes there. It costs O(n) stack room for no gain.

Remember this

Grown-up words: the boxes are nodes, the trailing finger is a trailing pointer, and moving the last k boxes to the front is a right rotation of the list.