【LeetCode刷题】反转链表


题目链接:反转链表

题目

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例2:
输入:head = [1,2]
输出:[2,1]

示例3:
输入:head = []
输出:[]

解题

题目不难,看大家得题解里面有用递归解决的,有用双指针解决的,还有用借助栈解决的,这里我用另外一种方法来解决——“尾插法”。学过数据结构得同学应该都知道,链表的插入有“头插法”和“尾插法”两种。顾名思义,“头插法”是在链表头部插入数据,“尾插法”则是在尾部插入数据。那么,我把输入的链表遍历,然后“尾插法”组织成一个新的链表,这样第一个元素不就变成了最后一个元素,以此类推,整个链表就完成了反转。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode header = new ListNode(); // 新链表的头节点

    public void insert(ListNode node) {
        // 头插法插入数据
        // 直接接收 原来的节点,而不是新建节点,节省空间
        node.next = header.next;  
        header.next = node;
    }

    public ListNode reverseList(ListNode head) {
        ListNode p = head;
        while(p != null) {
            p = head.next;
            head.next = null;
            insert(head);
            head = p;
        }

        return header.next; // 返回时记得去掉头
    }
}

只对链表遍历了一遍,时间复杂度:$O(n)$
只用了一个辅助节点(头节点),空间复杂度:$O(1)$

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【LeetCode刷题】反转链表


Just For Fun...