牛客网高频算法题系列-BM1 反转链表

题目描述

给定一个单链表的头结点pHead(该头节点是有值的)，长度为n，反转该链表后，返回新链表的表头。

原题目见：BM1 反转链表

解法一：结点反转

  • 首先，如果head为空或者只有一个结点，直接返回。
  • 否则，分别用first和next指针指向链表的前两个结点，并将它们的next指针域反转，然后继续往后遍历处理链表的后续结点直到将最后一个结点反转。注意，需要将head头结点的next指向null。
  • 最后，返回first结点，即为反转后的新链表的头结点。

解法二：递归法

  • 同样的，首先需要判断，如果head为空或者只有一个结点，直接返回。
  • 否则，通过递归的方式来处理，递归的处理流程如下：
    • 递归的终结条件是head结点为空或者没有下一个结点；
    • 否则，递归得到head.next的反转链表为reverse，然后将reverse的next指针指向head，同样要记住需要将head头结点的next指向null。
  1. public class Bm001 {
  2.     /**
  3.      * 反转结点
  4.      *
  5.      * @param head 原链表的头结点
  6.      * @return
  7.      */
  8.     public static ListNode reverseList(ListNode head) {
  9.         // 如果链表为空或者只有一个节点，不需要反转，直接返回原链表
  10.         if (head == null || head.next == null) {
  11.             return head;
  12.         }
  14.         ListNode first = head, second = head.next;
  15.         first.next = null;
  16.         while (first != null && second != null) {
  17.             ListNode temp = first;
  18.             first = second;
  19.             second = second.next;
  20.             first.next = temp;
  21.         }
  22.         return first;
  23.     }
  25.     /**
  26.      * 递归法
  27.      *
  28.      * @param head 原链表的头结点
  29.      * @return
  30.      */
  31.     public static ListNode reverseList2(ListNode head) {
  32.         // 递归的终止条件
  33.         if (head == null || head.next == null) {
  34.             return head;
  35.         }
  37.         // 递归处理
  38.         ListNode reverse = reverseList2(head.next);
  39.         head.next.next = head;
  40.         head.next = null;
  41.         return reverse;
  42.     }
  44.     public static void main(String[] args) {
  45.         // 测试用例
  46.         ListNode head = ListNode.testCase1();
  48.         System.out.println("反转之前");
  49.         ListNode.print(head);
  51.         System.out.println("反转之后");
  52.         ListNode newHead = reverseList(head);
  53.         ListNode.print(newHead);
  55.         System.out.println("再次反转之后");
  56.         ListNode newHead2 = reverseList2(newHead);
  57.         ListNode.print(newHead2);
  58.     }
  59. }

牛客网高频算法题系列-BM1 反转链表 - 图1
牛客网高频算法题系列-BM1 反转链表 - 图2
相信坚持的力量！