LeetCode（Linked List)206. Reverse Linked List

刺骨的言语ヽ痛彻心扉 2023-09-24 20:04 32阅读 0赞

# 1.问题 #

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

Example 1:

![在这里插入图片描述][4dc0c011dade4c08953671c4877a9ed9.png]

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

Example 2:  
![在这里插入图片描述][d9c8a48500ce4c7f97c56c42a2a4e18c.png]

> 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： ##

![在这里插入图片描述][7136ecc0cb8612a1a253c24155074c23.gif_pic_center_pic_center]

> 迭代方法解题

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

## 方法2： ##

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

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

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

![在这里插入图片描述][e3cd89fffea3492f8cc7d28cd58b7472.png]

# 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

[4dc0c011dade4c08953671c4877a9ed9.png]: https://img-blog.csdnimg.cn/4dc0c011dade4c08953671c4877a9ed9.png
[d9c8a48500ce4c7f97c56c42a2a4e18c.png]: https://img-blog.csdnimg.cn/d9c8a48500ce4c7f97c56c42a2a4e18c.png
[7136ecc0cb8612a1a253c24155074c23.gif_pic_center_pic_center]: https://img-blog.csdnimg.cn/img_convert/7136ecc0cb8612a1a253c24155074c23.gif#pic_center#pic_center
[e3cd89fffea3492f8cc7d28cd58b7472.png]: https://img-blog.csdnimg.cn/e3cd89fffea3492f8cc7d28cd58b7472.png