关于链表的反转

• 引用

LeetCode 206.反转链表

• 正文
  • 递归实现（运行77ms解决，效率极差）
    使用分治法的思想，拿到一个链表1-2-3-4-5，当你要反转这个链表的时候，你只需要得到2-3-4-5的反转，再加上1就可以了，同理2-3-4-5的反转就是将2-3-4反转，再结尾加上2便可。以此类推直到链表只剩下5，那5的反转就是自己本身再依次递归回去。

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) { val = x; }
   * }
   */
  class Solution {
      public ListNode reverseList(ListNode head) {
          if (head == null) return null;
          if (head.next == null) return head;
          else {
              ListNode node = reverseList(head.next);
              ListNode t = node;
              while (t.next != null) t = t.next;
              t.next = head;
              head.next = null;
              return node;
          }
      }
  }
  

  • 使用栈（运行4ms，效率差）
    使用栈暂存所有节点然后依次重新连接。

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) { val = x; }
   * }
   */
  class Solution {
      public ListNode reverseList(ListNode head) {
          if (head == null) return null;
          Stack<ListNode> stack = new Stack<>();
          ListNode t = head;
          while (t != null) {
              stack.push(t);
              t = t.next;
          }
          ListNode first = stack.pop();
          first.next = null;
          ListNode p = new ListNode(first.val);
          head = p;
          
          while (!stack.empty()) {
              ListNode a = stack.pop();
              a.next = null;
              p.next = a;
              p = p.next;
          }
          
          return head;
      }
  }
  

  • 迭代（运行不足1ms，效率高）
    从链表的首个位置取出元素指向新的链表，直到原链表不再拥有元素。

  /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) { val = x; }
  * }
  */
  class Solution {
      public ListNode reverseList(ListNode head) {
          if (head == null) return null;
          ListNode t = head;
          ListNode newList = null;
          ListNode p = head;
          while (t != null) {
              p = t.next;
              t.next = newList;
              newList = t;
              t = p;
          }
          return newList;
      }
  }