206. 反转链表

Contents

1. 1. 题目
2. 2. 思路

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

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

思路

迭代和递归方式

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = head;
        ListNode pre = null;
        if(node == null)return head;
        ListNode next = node.next;
        while(node != null && next!=null){
            node.next = pre;
            pre = node;
            node = next;
            next = node.next;
            
        }
        node.next = pre;
        return node;
    }
}

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null)return head;
        return reverse(head,null);
    }
    public ListNode reverse(ListNode node,ListNode exist){
        ListNode next = node.next;
        if(next == null){
            node.next = exist;
            return node;
        }
        node.next = exist;
        return reverse(next,node);
    }
}

官方解法

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