[数据结构与算法]链表反转java实现

算法题：实现链表的反转

提供了2种方法，迭代法、递归法。

（为了方便输出可视化，在自定义的ListNode中重写了toString方法。）

/**
 * Created By --- on 2021/8/12
 * 以下代码可以直接粘贴进编译器输出
 */
public class ReverseList {

  public static void main(String[] args) {
    ListNode head = new ListNode(3, new ListNode(5, new ListNode(8, new ListNode(9))));
    System.out.println("初始链表：" + head);

    ListNode newList = reverseList(head);
    System.out.println("使用迭代法反转链表：" + newList);

    ListNode newList2 = reverseList2(null, newList);
    System.out.println("使用递归法反转链表：" + newList2);
  }

  /**
   * 迭代法
   */
  public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    ListNode tmp;
    while (cur != null) {
      tmp = cur.next;
      cur.next = pre;
      pre = cur;
      cur = tmp;
    }
    return pre;
  }

  /**
   * 递归法
   */
  public static ListNode reverseList2(ListNode pre, ListNode cur) {
    if (cur == null) {
      return pre;
    }

    ListNode tmp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = tmp;
    return reverseList2(pre, cur);
  }


}


/**
 * singly-linked list
 */
class ListNode {

  int val;
  ListNode next;

  ListNode() {
  }

  ListNode(int val) {
    this.val = val;
  }

  ListNode(int val, ListNode next) {
    this.val = val;
    this.next = next;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder(String.valueOf(val));
    ListNode next = this.next;
    while (next != null) {
      sb.append(next.val);
      next = next.next;
    }
    return sb.toString();
  }
}

输出结果：

?

?