LeetCode（Linked List)206. Reverse Linked List

1.问题

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

在这里插入图片描述

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:
在这里插入图片描述

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

2. 解题思路

方法1：

在这里插入图片描述

迭代方法解题

初始化三个指针prev为NULL，curr为head，next为NULL。
遍历链表。
在循环中，在改变curr的next之前，存储下一个节点

方法2：

递归方法解题
将列表分为两部分——第一个节点和链表的其余部分。对链表的其余部分调用反向。将其余链表链接到第一个。将头指针固定为 NULL

头和具有 n-1 个节点的链表的其余部分（较小的问题）。
递归地反转具有（n-1）个节点的链表并返回该部分的头指针
反转后，head 的下一个节点将是最后一个节点，head 将指向该节点。
但是对于链表的完全反转，头部应该是最后一个节点。

head.next.next = head     
    head.next = NULL

在这里插入图片描述

3. 代码

代码1：

/**
 * 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,cur=head,next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        head=pre;
        return head;
    }
}

本地代码运行

package com.Amy.leecode;
class LinkedList {
    static ListNode head;
    public static ListNode reverseList(ListNode head){
        ListNode pre=null,cur=head,next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        head=pre;
        return head;
    }
    public static void push(int new_data) {
        ListNode new_node = new ListNode(new_data);
        new_node.next = head;
        head = new_node;
    }
    public void print(){
        ListNode node = head;
        while(node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
    }
    public static void main (String[]args){
        LinkedList list = new LinkedList();
        list.push(1);
        list.push(3);
        list.push(8);
        list.push(4);
        System.out.println("\nCreated Linked list is:");
        list.print();
        System.out.println("\n");
        head=list.reverseList(head);
        list.print();
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int value){
            val = value;
            next=null;
        }
    }
}
Created Linked list is:
4 8 3 1 
1 3 8 4

代码2：

/**
 * 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) {
        if(head ==null||head.next==null) return head;
        ListNode res = reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return res;
    }
}

本地代码运行

class LinkedList {
    static ListNode head;
    public static ListNode reverseList(ListNode head){
        if(head ==null||head.next==null) return head;
        ListNode res = reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return res;
    }
    public static void push(int new_data) {
        ListNode new_node = new ListNode(new_data);
        new_node.next = head;
        head = new_node;
    }
    public void print(){
        ListNode node = head;
        while(node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
    }
    public static void main (String[]args){
        LinkedList list = new LinkedList();
        list.push(1);
        list.push(3);
        list.push(8);
        list.push(4);
        System.out.println("\nCreated Linked list is:");
        list.print();
        System.out.println("\n");
        head=list.reverseList(head);
        list.print();
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int value){
            val = value;
            next=null;
        }
    }
}
Created Linked list is:
4 8 3 1 
1 3 8 4