Swift - LeetCode - K 개의 정렬 링크 통합

2028 단어
제목.
K 개 정렬 링크 병합
질문:
k 개의 정렬 링크 를 합 쳐 합 친 정렬 링크 를 되 돌려 줍 니 다.알고리즘 의 복잡 도 를 분석 하고 설명 하 십시오.
문제 풀이 방향:
여 긴 분 치 법 이 필요 해.쉽게 말 하면 쉬 지 않 고 반 으로 나 누 는 것 이다. 예 를 들 어 k 개의 링크 는 먼저 두 개의 k / 2 개의 링크 를 합병 하 는 임무 로 나 누고 한 개 또는 두 개의 링크 만 있 는 임무 로 나 눌 때 까지 계속 아래로 나 누 어 합병 하기 시작한다.예 를 들 어 6 개의 링크 를 합병 하면 분 치 법 에 따라 우 리 는 먼저 1 과 4, 2 와 5, 3 과 6 을 합병 한다.이렇게 하면 다음 에는 3 개의 링크 만 합병 하면 우 리 는 1 과 3 을 합병 하고 마지막 에 2 와 합병 하면 된다.
예시:
  :
     [
     1->4->5,
     1->3->4,
     2->6
     ]
  : 1->1->2->3->4->4->5->6

코드:
/**
public class SingNode {
    public var value : Int
    public var nextNode: SingNode?
    
    public init(value:Int) {
        self.value = value
    }
}
 **/
func merchageTotalList(_ list : [SingNode?]) -> SingNode? {
        guard list.count > 0 else {
            return nil
        }
        
        var left = 0
        var right = list.count - 1
        var lists = list
        
        while right > 0 {
            left = 0
            while left < right {
                lists[left] = merchgeTwoList(lists[left], lists[right])
                left = left + 1
                right = right - 1
            }
        }
        return lists[0]
    }

func merchgeTwoList(_ l1:SingNode?, _  l2:SingNode?) -> SingNode? {
        if l1 == nil {
            return l2
        }
        
        if l2 == nil {
            return l1
        }
        
        let dummy = SingNode.init(value: 0)
        var tempNode = dummy
        
        var L1 = l1
        var L2 = l2
        
        while L1 != nil && L2 != nil {
            if L1!.value < L2!.value {
                tempNode.nextNode = L1
                L1 = L1?.nextNode
            } else {
                tempNode.nextNode = L2
                L2 = L2?.nextNode
            }
            tempNode = tempNode.nextNode!
        }
        
        tempNode.nextNode = L1 ?? L2
        return dummy.nextNode
    }
    

좋은 웹페이지 즐겨찾기