题目信息

题目地址：https://leetcode-cn.com/problems/reverse-linked-list/submissions/

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解法一：迭代

反转一个链表和数组是不一样的，因为不能任意取值，只能说按照next的顺序依次往后放。那么把一个节点往后放的过程就是一次迭代

我们要迭代的有两个值，第一个不用说是当前节点cur每次迭代完它要换成原链表的下一个，第二个是转换过去的next，它是上一个当前节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode reverseList(ListNode head) {
    ListNode cur = head;
    ListNode next = null;
    while( cur != null){
        //记住原链表的下一个
        ListNode temp = cur.next;
        //设下next
        cur.next = next;
        //更新next与cur
        next = cur;
        cur = temp;
    }
    return next;
}

解法二：递归

有了这样一个迭代，我们可以去转一下递归。在迭代当中我们去设置了头结点的next为空，之后的next都是推导的，反过来它是我们的递归出口

我们通过reverseListc传入头结点，完成整个链表的反转。如果我们传入头结点的next呢，那么就从图中4的节点开始反转，最终要实现真正的反转把4节点指向5节点并且5节点指向null。

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
	if(head==null || head.next==null) {
		return head;
	}
	ListNode cur = reverseList(head.next);
    //最后操作 4指向5，且5指向null
	head.next.next = head;
	head.next = null;
	return cur;
}

解法三：栈

解这一题栈也是可以用，我们迭代顺着从头结点开始，把自己作为下一个被指向。那么倒着先从最后节点开始把它的next指向前一个节点。但是对于这个单向链表找下一个next就可以取到，但找前一个取不到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode reverseList(ListNode head) {
    Stack<ListNode> stack = new Stack<>();
    //依次入栈
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty()) return null;
    ListNode newHead = stack.pop();
    ListNode cur = newHead;
    //依次出栈，next为下一个
    while (!stack.isEmpty()) {
        ListNode temp = stack.pop();
        cur.next = temp;
        cur = cur.next;
    }
    //处理最后一个next为null,否则成环
    cur.next = null;
    return newHead;
}

总结

解法二关于递归的改造作为算法学习还是可以多练习的，解法一正向遍历+过程反向（每个把自己作为后一个也就是下一个在前面）解法三反向遍历+过程正向（每个都是前一个它的next就是下一个），总体来说解法一最优，解法二与三熟悉其他数据结构以及某些算法思想