反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路一 头插法

时间复杂度O(n)，空间复杂度O(n)

public ListNode ReverseList(ListNode head) {
    if(head == null || head.next == null)
        return head;
    ListNode linkedList = new ListNode(0);//头插法
    ListNode node = null;
    while (head != null){
        node = new ListNode(head.val);
        node.next = linkedList.next;
        linkedList.next = node;
        head = head.next;
    }
    return linkedList.next;
}

解题思路二

这是牛客@伊万夫斯基的思路

815472960_1566642098849_C3B4D3532589FC2990420BCEA62A8DBF.jpg

public ListNode ReverseList2(ListNode head) {
    if(head == null || head.next == null) //空链表或链表只有一个结点
        return head;
    ListNode pre = null;    //前一个结点
    ListNode next = null; //下一个结点
    while (head != null){
        //改变原有链表的指针指向
        next = head.next;//记录下一个结点的位置，避免断链
        head.next = pre; //当前结点指向前一个结点，实现反转
        pre = head; //pre向后一位
        head = next; //head向后一位
    }
    return pre;
}