Java实现链表反转的两种思路

题目

将单链表的连接顺序反转过来
输入:1->2->3->4->5
输出:5->4->3->2->1

迭代

迭代，即遍历整个链表的节点，在每个节点上进行操作。每个节点之间都需要进行三个步骤：1.保存下一个节点（因为要断开本节点与下个节点的连接，然后去连接上一个节点），2.保存上一个节点，3.本节点指向上一个节点。
代码如下：

    /**
     * 迭代反转链表
     * @param head
     * @return
     */
    public static ListNode iterate(ListNode head){
        ListNode node = head;
        ListNode prev = null,next;
        while (node!=null){
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

递归

    /**
     * 递归反转链表
     * @param head
     * @return
     */
    public static ListNode recursion(ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode newHead = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14