• 206.反转链表
  • 题目
  • 题解-迭代
  • 题解-递归

206.反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解-迭代

翻转肯定需要两个指针，pre -> cur （-> next ）换成 pre<-cur （next），当cur指向pre后，next断链了，为了防止断链，我们还需要保存下来next。更新pre和cur进行下一次翻转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode tmp;
        while(head!=null){
            tmp = head.next; //防止断链,记录下要反转的节点的后一个节点
            head.next = pre; //开始反转指向前一个
            pre = head; 
            head = tmp;
        }
        return pre;
    }
}

题解-递归

迭代是从前往后处理，递归则是先递到最后，再从最后归回来。

递归三部曲

递归终止条件
什么时候停止递归？反转链表，链表至少有2个元素，如果只有一个节点或者空节点就停止递归。

这里的返回值是什么呢？
返回反转后的头节点。

if(head==null || head.next == null){
	return head; //递归终止，遍历到了最后一个元素这个就是反转后的头节点或者当前链表为空
}

递归的参数和返回值
递归的返回值就是反转后头节点，也就是终止条件返回的节点，那么将这个返回值层层传递就行了。
递归的参数是单链表的头节点。

public ListNode reverseList(ListNode head)

本层递归的逻辑

ListNode ret = reverseList(head.next);
head.next.next = head;
head.next = null;
return ret; //层层传递反转后的头节点

代码

class Solution {
    ListNode pre =null;
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode temp = head.next;
        head.next = pre;
        pre = head;
        reverseList(temp);
        return pre;
    } 
}

题解中的整个流程图，便于理解递归。