【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)$