面试题 反转单链表

1、迭代法

2、递归法

Java 实现

class ListNode {    int val;    ListNode next;    ListNode(int val) {        this.val = val;        next = null;    }    @Override    public String toString() {        return val + "->" + next;    }}public class ReverseListedList {    public static void main(String[] args) {        ListNode head = new ListNode(1);        ListNode a = new ListNode(2);        ListNode b = new ListNode(3);        ListNode c = new ListNode(4);        ListNode d = new ListNode(5);        head.next = a;        a.next = b;        b.next = c;        c.next = d;        System.out.println("链表反转前：" + head);        head = reverseListByIterative(head);        System.out.println("迭代反转后：" + head);        head = reverseListByRecursive(head);        System.out.println("递归反转后：" + head);    }    public static ListNode reverseListByIterative(ListNode head) {        if (head == null)            return head;        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode prev = dummy.next;        ListNode pcur = prev.next;        while (pcur != null) {            prev.next = pcur.next;            pcur.next = dummy.next;            dummy.next = pcur;            pcur = prev.next;        }        return dummy.next;    }    public static ListNode reverseListByRecursive(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode newHead = reverseListByRecursive(head.next);        head.next.next = head;        head.next = null;        return newHead;    }}

运行结果

链表反转前：1->2->3->4->5->null迭代反转后：5->4->3->2->1->null递归反转后：1->2->3->4->5->null