206. 反转链表/面试题24. 反转链表(简单)

反转一个单链表。

示例:

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

进阶:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list

思路：

当前，后继，前驱

回看记录200521

就是交换节点，画图最好理解，注意返回的为pre

注意看这里面的演示

https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-hswxy/

代码1（非递归）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur =head,pre= null,temp = null;
        while(cur!=null){
            temp = cur.next;
            cur.next = pre;//三个指针轮指
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

代码2（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode reverseList(ListNode head) {
        //递归写法
        //结束条件
        if(head==null || head.next==null){
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next= head;
        head.next = null;
        return node;
    }
}