【LeetCode】24.두 개의 교환 체인 테이블의 노드
제목 설명
24. 두 개의 교환 체인 테이블의 노드
체인 테이블을 정하고 두 개를 교환하며 그 중 인접한 노드를 교환하고 교환된 체인 테이블을 되돌려줍니다.
너는 단순히 노드 내부의 값을 바꾸는 것이 아니라 실제적으로 노드 교환을 해야 한다.
：
1->2->3->4, 2->1->4->3.
제목 해석
방법1: 귀속
문제 풀이 사고방식
귀속의 문제 풀이 사고방식은 하위 문제를 다음 층의 귀속 함수 처리에 맡기는 데 있다. 그 자체는 이 단계의 문제에만 초점을 맞추고 귀속 함수 반환 값을 얻을 때 기본값은 이미 정확한 결과를 얻었기 때문에 현재 층의 논리만 계속 처리하면 된다.
본고는 두 개의 교환 체인 테이블 노드가 필요하기 때문에 헤드 노드head의 다음 노드next는 반드시 새로운 헤드 노드newHead이다. 그리고 귀속적인 방식으로 넥스트 노드 뒤의 체인 테이블을 교환하고 후속 체인 테이블 교환 노드를 얻은 후에 헤드 노드head의 넥스트 바늘에 직접 값을 부여한다. 넥스트 바늘은 newHead와head의 관련을 처리하고 교환된 체인 테이블을 얻는다.
코드 예제
Java:
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode swapPairs(ListNode head) {
// terminator
if (head == null || head.next == null) {
return head;
}
// recursion
ListNode newHead = head.next;
head.next = swapPairs(newHead.next);
// process data
newHead.next = head;
return newHead;
}
복잡도 분석
시간 복잡도: O(n)
공간 복잡도: O(n), 귀속 시 추가 창고 공간을 사용합니다.
방법2:교체
문제 풀이 사고방식
교체하는 방식은 모두가 비교적 익숙하다. 체인 표두 노드부터 훑어보고 두 개의 노드를 교환한다.노드를 교환하는 과정에서 주의해야 할 것은 체인 시계가 어느 위치까지 옮겨갔는지, 두 노드의 교환이 끝난 후에도 계속 뒤로 돌아다닐 수 있는지이다.
반복 해법에서prev와curr바늘을 통해 체인 테이블의 현재 역행 위치를 기록하고 두 노드의 교환이 끝난 후prev와curr바늘이 뒤로 이동하여 체인 테이블의 끝까지 노드 교환을 계속합니다.
코드 예제
Java:
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode swapPairs(ListNode head) {
ListNode newHead = new ListNode(0);
newHead.next = head;
ListNode prev = newHead, curr = head;
while(curr != null && curr.next != null) {
// next
ListNode next = curr.next;
//
curr.next = curr.next.next;
next.next = curr;
prev.next = next;
// prev，curr
prev = curr;
curr = curr.next;
}
return newHead.next;
}
복잡도 분석
시간 복잡도: O(n)
공간 복잡도: O(1)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
