牛客题霸题解

牛客题霸传送门：点击

NC78-反转链表

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

示例：

输入 {1,2,3}
返回值 {3,2,1}

题解：
1.迭代版本:

分析：因为是单链表，所以我们在迭代的时候前驱节点不能直接获取，我们需要一个额外的变量来保存前驱节点。然后改变当前节点的next前驱节点，同时保存后继节点。
空间复杂度：O(1)。
时间复杂度：O(n)。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
   public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
   }
}

2.递归

分析：先分析 reverseList 函数的功能：翻转一个链表，并返回新链表的头节点（原链表的尾节点）。所以我们可以先递归处理 reverseList，将以head.next为头节点的链表翻转，并得到原链表的尾节点，此时head.next是新链表的尾节点，我们令它的next指向head，并将head.next指向空即可将整个链表翻转。
空间复杂度：O(n)。
时间复杂度：O(n)。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
class Solution {
    public ListNode ReverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode curr, ListNode pre) {
        if (curr == null) {return pre;}
        ListNode next = curr.next;
        curr.next = pre;
        return reverse(next, curr);
    }
}

3.递归优化版本

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
class Solution {
 private ListNode listHead;
    public ListNode ReverseList(ListNode node) {
        if (node == null) return null;

        if (node.next == null) {
            listHead = node;
            return listHead;
        }
        ReverseList(node.next);
        node.next.next = node;
        node.next = null;
        return listHead;
    }    
}

户枢不蠹，流水不腐