单向链表的翻转

思路：

通过递归方法，存储一个临时指向前一个节点变量，将当前链表 next 指向上一个节点达到翻转效果。

• 单向链表

• 第一步

• 第二步

• 第三步

• 第四步

• 第五步

实现示例

class LinkList {
  public next: LinkList;
  public data: number;
  constructor(data: number) {
    this.data = data;
  }
}

// 循环解法
function reverseLinkList(data: LinkList) {
  let head = data;
  let tmp = null;
  while (head) {
    const next = head.next;
    head.next = tmp;
    tmp = head;
    head = next;
  }
  return tmp;
}

// 递归处理
function reverseLinkListRecursion(pre: LinkList, head: LinkList) {
  if (!head) return pre;
  let next = head.next;
  head.next = pre;
  return reverseLinkListRecursion(head, next);
}

let node1 = new LinkList(1);
let node2 = new LinkList(2);
let node3 = new LinkList(3);
let node4 = new LinkList(4);
let node5 = new LinkList(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;

console.log(node1);

const h = reverseLinkList(node1);
console.log(h);

console.log(reverseLinkListRecursion(null, h));