题解 | #反转链表#，但是haskell foldl

在Haskell中，list就是单链表。反转list的函数reverse经常被很酷地定义为

reverse = foldl (flip (:)) []

-- 其中 foldl可以被看作 --
foldl f z []     = z
foldl f z (x:xs) = let z' = z `f` x in foldl f z' xs

-- cons则是简单的将x放在xs前面 --

因此我们定义 cons 和 (foldl (flip (:))) 两个函数，再手动模拟foldl，就可以写出如下的酷炫代码。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode ReverseList(ListNode head) {
        return foldWithCons(null, head);
    }

    public ListNode foldWithCons(ListNode z, ListNode ls) {
        /*
        Recall that in haskell, lists are singly linked list, and reverse is foldl (flip (:)) []
        foldl f z []     = z
        foldl f z (x:xs) = let z' = z `f` x in foldl f z' xs
         */
        if (ls == null) {
            return z;
        } else {
            ListNode x = ls;
            ListNode xs = ls.next;
            ListNode z_ = cons(x, z); // flip cons z x
            return foldWithCons(z_, xs);
        }
    }


    /**
     * cons :: x -> [x] -> x
     * prepend x to list xs
     *
     * @param x ListNode x
     * @param xs  list of x
     * @return ListNode to x, following which is xs
     */
    public ListNode cons(ListNode x, ListNode xs) {
        x.next = xs;
        return x;
    }
}