Golang 통합 체인 테이블에서 채팅 귀속

합병 체인 테이블에서 차례로 돌아가다

귀속은 엔지니어가 가장 흔히 볼 수 있는 문제를 해결하는 방식이지만, 때로는 진정으로 파악하기가 쉽지 않다.어떤 사람은 보기에는 매우 간단해 보이지만, 스스로 쓰기에는 좀 힘이 든다고 말한다.
가장 유명한 예는 피보나치 수열(Fibonacci sequence)으로 점차적 공식을 찾아 결과를 계산한다.최근에 나온 통합 체인 테이블의 알고리즘 문제도 귀환으로 실현할 수 있다.다음은 제목 설명을 살펴보겠습니다.

     。 。

 ：

 ：1->2->4, 1->3->4
 ：1->1->2->3->4->4

 ： （LeetCode）

먼저 본인의 관점을 내놓고 귀환의 관건은 경계 조건과 귀환 공식을 찾는 것이다.
제목을 분석하면 첫 번째 체인표 l1의 머리 노드로 l2의 노드와 비교할 수 있다. 만약에 l2의 현재 노드보다 크면 l1의next와 l2의 크기를 계속 비교할 수 있다.반대로 l1의 헤드 노드가 L2의 현재 노드보다 작다면 l2에 대해 유사한 처리를 해야 한다.이런 끊임없는 대비와 편이의 과정은 일종의 귀속 공식을 총결해 낼 수 있다.위조 코드로 쓰는 방법은 다음과 같다.

if l1.val < l2.val:
    l1.next = mergeTwoList(l1.next, l2)
    
    return l1
else:
   l2.next = mergeTwoList(l1, l2.next)
   return l2

경계 조건은 끊임없이 이동할 때 어떤 체인 테이블의 마지막 노드에 도착할 때까지 위조 코드는 다음과 같다.

if l1 === null:
    return l2

if l2 === null:
    return l1

Golang으로 구현되며 코드도 명확합니다.

type ListNode struct {
	Val int
	Next *ListNode
}

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(l1, l2.Next)
		return l2
	}
}

LeetCode에서 제출한 실행 피드백은 다음과 같습니다.

 ：
 
 
 ：
0 ms
,   Go  
100.00%
 
 ：
2.6 MB
,   Go  
63.64%
 

귀환은 메모리를 매우 소모하는 것으로, 마치 루즈벨트처럼, 한 층 한 층 내층으로 돌아가는 호출 결과를 볼 수 있다.
최적화를 위해 교체 방식을 사용할 수 있으며 코드는 몇 가지 조정이 필요합니다.

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
	result := head
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			head.Next = l1
			head = head.Next
			l1 = l1.Next
		} else {
			head.Next = l2
			head = head.Next
			l2 = l2.Next
		}
	}

	if l1 == nil {
		head.Next = l2
	}

	if l2 == nil {
		head.Next = l1
	}

	return result.Next
}

오프셋을 하기 위해 머리 포인터를 만들어야 하고, 최종적으로result는 합성 결과 체인 테이블로 결과를 저장해야 한다는 것을 알 수 있다.마지막으로 실행을 제출하였는데 결과 데이터가 약간 보기 좋았습니다.

 ：
4 ms
,   Go  
62.28%
 
 ：
2.5 MB
,   Go  
100.00%
 

데이터의 양이 크지 않은 상황에서 사실 성능의 차이도 크지 않기 때문에 귀속을 사용하는 것도 문제가 없다.