数据结构之反转链表 | 春日游, 杏花吹满头

反转一个单链表

示例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

分析

可以通过递归或迭代, 将下一个节点的指针指向上一个节点完成反转

代码

Python3(迭代)

def reveser(self, head):
  prev = None
  current = head
  while current:
    temp = current.next
    current.next = prev
    prev = current
    current = temp
  return prev

Python3(递归)

def reveser(self, head):
  if not head or not head.next:
    return head
  nextNode = self.reveser(head.next)
  head.next.next = head
  head.next = None
  return nextNode

JavaScript(迭代)

function reveser(self, head) {
  let prev = null
  let current = head

  while(current) {
    let temp = current.next
    // 当前节点的next指向上一个节点
    current.next = prev
    // 上一个节点变为当前节点, 反转过程完成
    prev = current
    // 迭代后续节点
    current = temp 
  }
  return prev
}

JavaScript(递归)

function reveser(head) {
  if (head === null || head.next === null) return head
  let nextNode = reveser(head.next)
  head.next.next = head
  head.next = null
  return nextNode
}