LeetCode: 24. Swap Nodes in Pairs

LeetCode: 24. Swap Nodes in Pairs

Problem: 24. Swap Nodes in Pairs

Link: https://leetcode.com/problems/swap-nodes-in-pairs/

Difficulty: Hard

Description:

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Solution:

Language: Swift

Runtime: 116ms
Memory: 25.3MB

Copy to Clipboard

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        if lists.isEmpty {
            return nil
        }
        if lists.count == 1 {
            return lists[0]
        }
        
        let middle = lists.count / 2
        let left = mergeKLists(Array(lists[0 ..< middle]))
        let right = mergeKLists(Array(lists[middle...]))
        
        return mergeTwoLists(left, right)
    }
    
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        if l1 == nil {
            return l2
        }
        if l2 == nil {
            return l1
        }
        
        if l1!.val < l2!.val {
            l1!.next = mergeTwoLists(l1!.next, l2)
            return l1
        } else {
            l2!.next = mergeTwoLists(l2!.next, l1)
            return l2
        }
        return nil
    }
}

Related Posts

Leave A Comment Cancel reply