问题

反转一个单链表

示例
输入：1->2->3->4->5->NULL
输出：5->4->3->2->1->NULL

思路

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表

  • 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null
  • 接着把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点；保存这个节点的目的是因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了
  • 紧接着，继续移动pre和cur指针
  • 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点

双指针法

  1. public class leetcode_206_1 {
  2.     public ListNode reverseList(ListNode head) {
  3.         ListNode prev = null;
  4.         ListNode curr = head;
  5.         while(curr != null){
  6.             ListNode nextTemp = curr.next; // 保存cur的下一个节点，接下来要改变cur->next
  7.             curr.next = prev; //翻转
  8.             prev = curr;
  9.             curr = nextTemp;
  10.         }
  11.         return prev;
  12.     }
  13. }
  • 时间复杂度：leetcode-206：反转链表 - 图1
  • 空间复杂度：leetcode-206：反转链表 - 图2

递归法

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         if (head == null || head.next == null) {
  4.             return head;
  5.         }
  6.         // curr——最后一个节点
  7.         ListNode curr = reverseList(head.next);
  8.         head.next.next = head;
  9.         head.next = null; //没有这一段，代码可能会进入循环
  10.         return curr;
  11.     }
  12. }
  • 时间复杂度：leetcode-206：反转链表 - 图3，n 列表长度
  • 空间复杂度：leetcode-206：反转链表 - 图4，递归会使用隐式栈空间，递归深度可能达到 n 层