[알고리즘] 알고리즘 패턴 정리 1 (연결 리스트 편, LinkedList)

연결 리스트 편 (Linked List)

 

1. 러너 기법을 이용하는 패턴

2개의 러너 slow와 fast, 2개의 포인터를 이용하여 연결 리스트를 순회하는 기법
빠른 러너(fast)는 느린 러너보다 두 배로 이동합니다.
fast가 끝에 도달하면, slow는 중간 노드에 위치하는데요.
 
이런 특성을 이용해서, 중간 위치를 찾아 낼 수 있습니다.
예시)
1) 값을 비교하기
2) 뒤집기
3) 팰린드롬 찾기
 
 

 
 
 
 
 

2. node.next != null && node.next.next !== null 인 조건을 체크하기

node 다음 노드를 a,
node 다음+다음 노드를 b라고 할 때,
 
node와 a, b 를 이용해서,
현재 노드와 다음 노드, 다다음 노드를 Swap 하는 등의 작업을 할 수 있습니다.
 
 

let node = new ListNode(0);
const root = node;

while (node.next !== null && node.next.next !== null) {
	const a = node.next;
    const b = node.next.next;
    
    a.next = b.next;
    node.next = b;
    node.next.next = a;

	node = node.next.next;
}

...

 
 
 
 
 
 

3. prev, curr, next 를 이용하기

while 문 안에서, curr = curr.next로 노드를 순회할 때,
prev, curr, next를 이용해, 이전 노드와 현재 노드, 다음 노드를 기억할 수 있습니다.
 
이를 이용해, 노드의 값을 swap하거나 뒤집을 수 있다.
 

type NodeType = ListNode | null;

let prev: NodeType = null;
let curr: NodeType = head;

// prev에 이전 노드를 계속 붙이면서, 역순으로 연결 리스트를 뒤집음
while (curr) {
	const next = curr.next;
    
	curr.next = prev;
    prev = curr;
    curr = next;
}

...

 
 
 
 

같이 알아보면 좋은 자료구조 : 스택, 데크(deque)