[LC 142]. Linked List Cycle II

数学题。容易想到用slow和fast两个pointer。但如何让两个pointer在circle起点处meet?首先搞清一个问题:假设circle length是r,list起点到circle起点距离是s,list起点到第一次相遇距离是k,circle起点到第一次相遇点距离是m,即s+m=k。由于k是slow和fast相遇点,所以2k-k = nr,n是一个整数。所以k = nr, s + m = nr。也就是说 s steps 和 m steps 加起来就是一圈。那么k的位置,距离circle起点已经走了m步,所以如果两个pointer分别从list起点和k处出发的,每人一次只走一步的话,那么他们会相遇在circle起点处。

circle

[LC 206]. Reverse Linked List

两种方法:Iteration 和 recursion。
Iteration:
1 ——–> 2 ——–> 3
newhead head temp

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

Recursion:同样是顺序的反转

    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    
    private ListNode reverse(ListNode head, ListNode newhead) {
        if (head == null) return newhead;
        ListNode next = head.next;
        head.next = newhead;
        return reverse(next, head);
    }

[LC 234]. Palindrome Linked List

算法好想,先找出整个list的长度,然后找到mid pointer,反转前半个list,以mid point为出发点同时向左右两个方向比较node的val。

写出clean code并不是很容易。以下是一个比较clean的版本,学习一下。用slow和fast两个pointer找mid point,fast速度是slow的二倍,在找mid point的同时反转前半个list。

    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode p1 = head; // slow, left part start
        ListNode p2 = head; // fast
        ListNode p3 = p1.next; // right part start
        ListNode pre = p1;
        
        // find mid pointer, reverse left part
        while (p2.next != null && p2.next.next != null) {
            p2 = p2.next.next;
            pre = p1; 
            p1 = p3;
            p3 = p3.next;
            p1.next = pre;
        }
        
        // for odd length, left more p1
        if (p2.next == null) {
            p1 = p1.next;
        } else { // even length, do nothing
            
        }
        
        while (p1 != null && p3 != null) {
            if (p1.val != p3.val) return false;
            p1 = p1.next;
            p3 = p3.next;
        }
        
        return true;
        
    }

Tip: 1. 11 – 13行,当需要更新多个pointer时,尝试从最左到最右依次更新,以避免出错。
2. 19行,注意此时前半个list已经反转,所以p1 move left是p1.next不是p3.

可以交流是否需要保持原输入list不变,如果需要,还要在后面比较的过程中还原输入。不过在以上code基础上修改就会比较难看。

   public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        ListNode p1 = head; 
        ListNode p2 = head;
        ListNode p3 = p1.next; 
        ListNode pre = p1;
        
        while (p2.next != null && p2.next.next != null) {
            p2 = p2.next.next;
            pre = p1;
            p1 = p3;
            p3 = p3.next;
            p1.next = pre;
        }
        
        ListNode next = p3;    // restore
        if (p2.next == null) {
            ListNode tmp = p1; // 
            p1 = p1.next;
            tmp.next = p3;     // 
            next = tmp;        // 
        } 

        while (p1 != null && p3 != null) {
            if (p1.val != p3.val) return false;
            ListNode tmp = p1; //
            p1 = p1.next;
            p3 = p3.next;
            tmp.next = next;   // 
            next = tmp;        // 
        }

        return true; 
    }

[LC 25]. Reverse Nodes in k-Group

对于LinkedList调换node顺序的问题,通常需要牵扯到previous, current, next三种类型的node,或者需要记录head在哪,以便最后返回。这类问题一个普遍的思路是加dummy node:


ListNode dummy = new ListNode(0);
dummy.next = head;

类似的问题还有[LC 24] swap pairs 和 [LC 61] rotate list。对[LC 61]来说,加dummy还有一个好处,就是不需要考虑k%len == 0, 即不需要rotate的情况。下面三行是rotate的code,顺序是不能变的,变了之后不保证k%len == 0的情况也对。

需要rotate的情况:0->1->2->3->null, k = 2, tail = 3, newtail = 2, dummy = 0.

tail.next = dummy.next; // 0, 3->1->2->3
dummy.next = newtail.next; // 0->3->1->2->3
newtail.next = null; // 0->3->1->2->null

不需要rotate的情况:0->1->2->null, k = 2, tail = newtail = 2, dummy = 0

tail.next = dummy.next; // 0, 2 -> 1 -> 2
dummy.next = newtail.next; // 0->1<->2
newtail.next = null; // 0->1->2->null

对于本题[LC 25],操作略复杂,容易不知所措。首先想到需要两个循环,外面的循环iterate over groups, 里面的循环reverse current group。对外面的循环,循环内部有两步,Step 1. 判断当前group是否完整;Step 2. reverse group。对于Step 1,容易搞不清现在是找到第k个还是第k-1个了,找一个小例子验证一下。对于Step 2,是进行的以下操作:

0(dummy)->1->2->3->next 变成 0->2->3->1->next, 变成0->3->2->1->next

即不断取出prev后面的node,插到tail的后面

        while (true) {
            // Step 1: is this group complete or ending early
            int count = k;
            while (count &gt; 0 &amp;&amp; tail != null) {
                count--;
                tail = tail.next;
            }
            if (tail == null) break; // reach the end 

            // Step 2: reverse group
            head = prev.next;
            while (prev.next != tail) {
                tmp = prev.next;
                prev.next = tmp.next;
                tmp.next = tail.next;
                tail.next = tmp;
            }

            prev = head;
            tail = head;
        }

[LC 24]. Swap Nodes in Pairs

LinkedList的题关键是想清楚操作过程。例如本题,既然是swap pair,那么成对和不成对两种情况可以分开考虑。如果不成对,那么意味着list到结尾了,所以放在最后考虑,循环里只考虑成对的情况。对当前的一个pair,例如v1->v2 变成 v2->v1,v2.next = v1.next 是不会造成任何错误的,v1.next需要注意,是下一对swap后的头,可以在下一个循环中赋值。


public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode newhead = head.next;
    ListNode nextpair = head;
    ListNode lastend = null;
    while (nextpair != null && nextpair.next != null){ // only for pairs
        ListNode node1 = nextpair;
        ListNode node2 = nextpair.next;
        nextpair = nextpair.next.next; // head of next pair

        node2.next = node1; // swap the current pair
        if (lastend != null) {
            lastend.next = node2; // finish pointing the end of last pair to the head of this pair
        }
        lastend = node1; // remember the end of this pair
    }
    if (lastend != null) {
        lastend.next = nextpair; // if current pair is solo node,
// no need to swap, only point the end of last pair to the current node;
// if there is no more pairs,
// set the end of last pair to null, which is also the head of the current pair
    }
    return newhead;
}

需要牵扯到前,中,后,三个node的问题,也可以考虑一种通用的做法,就是在最开始加dummy node。这个问题中,pointer每往后移动一个pair,原来指向dummy的pointer就会指向前一个pair的tail。考虑以下code,比第一段可能更加清晰:

    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) { //依然只考虑pair
            ListNode first = cur.next;
            ListNode second = cur.next.next;
            cur.next = second; // 依次是cur,first和second的next赋值
            first.next = second.next;
            second.next = first;
            cur = cur.next.next;
        }
       return dummy.next;//之前已经将current pair的tail的next赋值成了下一个pair的head,如果下一个pair不完整,则什么都不需要做。
    }