notes | Kisstar

# 反转链表

反转单向链接的列表。

# Input: 1->2->3->4->5->NULL
# Output: 5->4->3->2->1->NULL

# 思路

我们用 cur 来存储当前节点，初始时第一个节点反转后的后继节点为空，之后每个节点的后继节点为前一个节点，我们用 prev 来存储前一个节点。

中途我们在设置当前节点的后继节点时，需要先用 temp 来保存当前节点原先的后继节点。

具体的操作表现为：

  1. 判断当前节点是否为空。
  2. 存储当前节点原先的后继节点。
  3. 设置当前节点的后继节点后，也就是原先的前一个节点。
  4. 指定下一个节点的后继节点，也就是当前节点。
  5. 指定下一个节点，也就是我们临时存储的当前节点原先的后继节点。
  6. 循环。

# JavaScript

var reverseList = function (head) {
  var cur = head,
    temp = null,
    prev = null
  while (cur) {
    temp = cur.next
    cur.next = prev
    prev = cur
    cur = temp
  }
  return prev
}

# Python

def reverseList(self, head: ListNode) -> ListNode:
    cur, pre = head, None
    while cur:
        cur.next, pre, cur = pre, cur, cur.next
    return pre

# Rust

补充描述：

  1. 添加 prev 变量用来指向上一个已处理的节点（最开始的节点应该为 None）
  2. 添加 curr 变量指向当前正在处理的节点
  3. 添加 next 变量（在当前节点不为空的情况下指向当前节点的下一个节点，也就是待处理的节点）
  4. 如果当前节点如果不为空，则开始处理当前节点
    1. 首先更新待处理的节点为当前节点的下一个节点（必须先记录，否则修改当前节点后就获取不到了）
    2. 更新正在处理的节点的 next 字段指向上一个已处理的节点
    3. 当前节点已处理，所以更新上一个节点为当前节点
    4. 更新当前节点为下一个待处理的节点
  5. 重复第 4 步，直到当前处理的节点为空而退出循环，并返回上一个已经处理好的节点
impl Solution {
  pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut curr = head;

    while !curr.is_none() {
      let mut curr_value = curr.unwrap();
      let next = curr_value.next;

      curr_value.next = prev;
      prev = Some(curr_value);
      curr = next;
    }

    prev
  }
}

← 相交链表 →