当前位置：首页 > article >正文

反转链表（Leetcode）

article 2024/11/8 21:50:02

反转链表

Leetcode题目链接

题意：翻转一个单链表

🌰:

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

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

在链表本身进行反转即可，不用重新定义链表，这同时浪费时间和空间。

需要采用哑节点吗？
不需要的，如果使用了哑节点还会造成报错。
如果给原链表添加哑节点：
dummy ->1->2->3->4->5->NULL
那么我们反转后就变成了：
5->4->3->2->1->dummy
这是不合理的，所以不使用哑节点。
还有一个问题，循环判断的条件是什么？
在该问题中，当链表被遍历到末尾后，程序便结束。
所以需要一个条件来确定链表是否已经被遍历到末尾。
代码如下：

class Solution{
  public ListNode reverseList(ListNode head){
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;
    while(cur != null){
       next = cur.next;
       cur.next = pre;
       pre = cur;
       cur = next;
    }
      //注意，反转链表后，原来的末尾成为现在的头
     return pre; 
  }
}

递归方法：

// 递归 
// 递归的核心思路和双指针是一样的。
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        // 注意递归出来的条件，当前节点为null，表明已经遍历完成
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}