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
还没有评论,来说两句吧...