力扣算法 - 反转链表

反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

Java解法

    /**
     * 头插法
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }
    /**
     * 递归思想
     * 注意:  可以假设 reverseList 函数已经实现功能
     * head = 1
     * 调用 reverseList(head.next) 相当于  reverseList(2)  这个函数假设已经实现反转 null 5 4 3 2
     * 只需要单独处理 head 节点 2.next = 1  , 2.next = null
     * 递归处理 直到head为null
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }

Swift解法

    // 递归法
    func reverseList1(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        let newHead: ListNode? = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        
        return newHead
    }
     
    // 头插法
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        var headTemp = head
        
        var newHead: ListNode? = nil
        while headTemp != nil {
            let temp = headTemp?.next
            headTemp?.next = newHead
            newHead = headTemp;
            headTemp = temp
        }
        
        return newHead
    }