Reverse Linked List

描述

Reverse a singly linked list.

分析

用三个指针 tail,p,q，紧紧相邻，不断前进，每次将p.next指向tail，将q.next指向p。

解法1 迭代

  1. // Reverse Linked List
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. public class Solution {
  4.     public ListNode reverseList(ListNode head) {
  5.         if (head == null || head.next == null) return head;
  7.         ListNode tail = null;
  8.         ListNode p = head;
  9.         ListNode q = p.next;
  11.         while (q != null) {
  12.             ListNode old = q.next;
  13.             p.next = tail;
  14.             q.next = p;
  16.             tail = p;
  17.             p = q;
  18.             q = old;
  19.         }
  20.         return p;
  21.     }
  22. }

解法2 递归

  1. // Reverse Linked List
  2. // Time Complexity: O(n), Space Complexity: O(n)
  3. public class Solution {
  4.     public ListNode reverseList(ListNode head) {
  5.         if (head == null || head.next == null) return head;
  7.         ListNode tail = head.next;
  8.         head.next = null;
  9.         ListNode newHead = reverseList(tail);
  10.         tail.next = head;
  12.         return newHead;
  13.     }
  14. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/linked-list/reverse-linked-list.html