问题描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路

1. 迭代

  1. public ListNode reverseList(ListNode head) {
  2.     if (head == null || head.next == null) {
  3.         return head;   
  4.     }
  5.     ListNode curr = head;    //待处理结点
  6.     ListNode prev = null;   //当前的头结点
  8.     while (curr != null) {
  9.          ListNode temp = curr.next;
  10.         curr.next = prev;
  11.         prev = curr;
  12.         curr = temp;
  13.     }
  14.     return prev;
  15. }

2. 递归

主要原理：递归执行过程即向下查找，向上返回
向下查找：找到链表的末节点p
向上返回：向上返回p（p在向上返回的过程中指代的节点没变）
只是在向上返回的过程中，捎带着改变下相邻节点的指向关系，逻辑如下

head.next.next = head;
head.next = null;

  1. public ListNode reverseList(ListNode head) {
  2.     //递归结束条件，链表为空或者只有一个节点
  3.     if (head == null || head.next == null) {
  4.         return head;
  5.     }
  6.     //递
  7.     ListNode p = reverseList(head.next);
  8.     //归
  9.     head.next.next = head;
  10.     head.next = null;
  12.     return p;
  13. }

个人理解

递归.pdf

并查集的路径压缩