LeetCode(Linked List)206. Reverse Linked List

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

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:

在这里插入图片描述

迭代方法解题

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

方法2:

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

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

  1. head.next.next = head
  2. head.next = NULL

在这里插入图片描述

3. 代码

代码1:

  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. * int val;
  5. * ListNode next;
  6. * ListNode() {}
  7. * ListNode(int val) { this.val = val; }
  8. * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9. * }
  10. */
  11. class Solution {
  12. public ListNode reverseList(ListNode head) {
  13. ListNode pre=null,cur=head,next=null;
  14. while(cur!=null){
  15. next=cur.next;
  16. cur.next=pre;
  17. pre=cur;
  18. cur=next;
  19. }
  20. head=pre;
  21. return head;
  22. }
  23. }

本地代码运行

  1. package com.Amy.leecode;
  2. class LinkedList {
  3. static ListNode head;
  4. public static ListNode reverseList(ListNode head){
  5. ListNode pre=null,cur=head,next=null;
  6. while(cur!=null){
  7. next=cur.next;
  8. cur.next=pre;
  9. pre=cur;
  10. cur=next;
  11. }
  12. head=pre;
  13. return head;
  14. }
  15. public static void push(int new_data) {
  16. ListNode new_node = new ListNode(new_data);
  17. new_node.next = head;
  18. head = new_node;
  19. }
  20. public void print(){
  21. ListNode node = head;
  22. while(node!=null){
  23. System.out.print(node.val+" ");
  24. node = node.next;
  25. }
  26. }
  27. public static void main (String[]args){
  28. LinkedList list = new LinkedList();
  29. list.push(1);
  30. list.push(3);
  31. list.push(8);
  32. list.push(4);
  33. System.out.println("\nCreated Linked list is:");
  34. list.print();
  35. System.out.println("\n");
  36. head=list.reverseList(head);
  37. list.print();
  38. }
  39. static class ListNode {
  40. int val;
  41. ListNode next;
  42. ListNode(int value){
  43. val = value;
  44. next=null;
  45. }
  46. }
  47. }
  48. Created Linked list is:
  49. 4 8 3 1
  50. 1 3 8 4

代码2:

  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. * int val;
  5. * ListNode next;
  6. * ListNode() {}
  7. * ListNode(int val) { this.val = val; }
  8. * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9. * }
  10. */
  11. class Solution {
  12. public ListNode reverseList(ListNode head) {
  13. if(head ==null||head.next==null) return head;
  14. ListNode res = reverseList(head.next);
  15. head.next.next=head;
  16. head.next=null;
  17. return res;
  18. }
  19. }

本地代码运行

  1. class LinkedList {
  2. static ListNode head;
  3. public static ListNode reverseList(ListNode head){
  4. if(head ==null||head.next==null) return head;
  5. ListNode res = reverseList(head.next);
  6. head.next.next=head;
  7. head.next=null;
  8. return res;
  9. }
  10. public static void push(int new_data) {
  11. ListNode new_node = new ListNode(new_data);
  12. new_node.next = head;
  13. head = new_node;
  14. }
  15. public void print(){
  16. ListNode node = head;
  17. while(node!=null){
  18. System.out.print(node.val+" ");
  19. node = node.next;
  20. }
  21. }
  22. public static void main (String[]args){
  23. LinkedList list = new LinkedList();
  24. list.push(1);
  25. list.push(3);
  26. list.push(8);
  27. list.push(4);
  28. System.out.println("\nCreated Linked list is:");
  29. list.print();
  30. System.out.println("\n");
  31. head=list.reverseList(head);
  32. list.print();
  33. }
  34. static class ListNode {
  35. int val;
  36. ListNode next;
  37. ListNode(int value){
  38. val = value;
  39. next=null;
  40. }
  41. }
  42. }
  43. Created Linked list is:
  44. 4 8 3 1
  45. 1 3 8 4

发表评论

表情:
评论列表 (有 0 条评论,192人围观)

还没有评论,来说两句吧...

相关阅读