LeetCode第206题 – 反转链表

76 views

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

  • 基于递归实现
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode last = null;
        
        ListNode n = null;
        // 找到数据中的最后一个节点
        n = head;
        while (n != null) {
            last = n;
            n = n.next;
        }
        
        reverseList(head, last);
        return last;
    }
    
    public ListNode reverseList(ListNode head, ListNode tail) {
        if (head == tail) {
            return head;
        }
        
        ListNode last = reverseList(head.next, tail);
        last.next = head;
        head.next = null;
        
        return head;
    }
}
  • 基于迭代实现
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode last = null;
        
        ListNode n = null;
        // 找到数据中的最后一个节点
        n = head;
        while (n != null) {
            last = n;
            n = n.next;
        }
        
        ListNode h = head;
        ListNode c = h;
        while (h != last) {
            h = c.next;
            c.next = last.next;
            last.next = c;
            c = h;
        }
        return last;
    }
}

要点
单链表的常规操作,注意保护头指针和尾指针,避免丢失。
使用递归时,注意退出条件,避免栈溢出;同时注意递归的返回结果并不是最终的结果。



若非注明,均为原创,欢迎转载,转载请注明来源:LeetCode第206题 – 反转链表

关于 JackieAtHome

基层程序员,八年之后重新启航

此条目发表在 Java, LeetCode 分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Protected with IP Blacklist CloudIP Blacklist Cloud