리트코드를 나홀로 스터디하고 정리한 내용입니다.
singly linked list 문제를 1. hast set, 2. floyd's tortoise and hare method로 푸는 설명을 담았습니다.
Two pointers
Two-pointer techinque에는 2가지의 시나리오가 존재한다.
1. starts at different position
2. moved at different speed (slow-pointer and fast-pointer problem)
전자는 두개의 포인터가 각각 다른 위치(처음과 끝)에서 움직이는 것이고,
후자는 각각의 포인터가 다른 스피드(하나는 빠르게 다른 하나는 느리게)로 움직이는 것이다.
만약 singly linked list 구조에서 문제를 푼다면 linked list의 순회가 한방향으로 밖에 이뤄지지 못하므로 2번 방식으로 접근해서 풀어야한다.
Template for two pointer in linked list (C++)
문제를 위한 C++ template
ListNode* slow = head;
ListNode* fast = head;
/**
* Change this condition to fit specific problem.
* Attention: remember to avoid null-pointer error
**/
while(slow && fast && fast->next){
slow = slow->next; // move slow pointer one step each time
fast = fast->next->next; // move fast pointer two steps each time
if(slow==fast){ // change this condition to fit specific problem
return true;
}
}
return false; // change return value to fit specific problemTips
- next field 접근 전에 node가 null인지 체크할 것.
fast = fast.next.next하기 전에 fast와 fast.next가 null이 아니여야함. - loop의 end condition을 잘 define할 것.
time & space complexity
two pointer의 경우
- space complexity: O(1) , 만약 포인터만 쓰고 다른 extra space없다면
- time complexity: O(N) , 이때 N은 list의 길이
141. Linked list cycle
Singly linked-list에서 cycle이 존재하는지 찾는 문제.
1. Hash table(set)이용
- linked list를 head부터 순회하면서 차례차례 hash set에 담게 되는데 이때 hash set내부에 이미 해당 노드가 존재한다면 cycle이 존재하는 것이고 해당 노드가 cycle의 시작점이 된다.
- Floyd's Tortoise and Hare(Fast pointer and slow pointer)
-
slow와 slow*2 distance를 가지는 fast 라는 두 포인터를 가지고 문제를 푼다. cycle이 존재한다면 cycle(원)을 돌다가 결국 두 포인터가 만나게 된다는 데서 착안한 방법이다.
-
아래 그림에서 1.은 cycle이 존재하지 않는 case를 다루고 있다. cycle이 존재하지 않는다면 결국 slow보다 빠른 fast가 null을 가리키게 될텐데 cycle의 length가 even인지 odd인지에 따라,
fast가 null 일때 끝나거나 fast->next가 null일때 끝나게 된다.
왜냐하면, fast가 slow의 2배 속력이므로 우리는 fast = fast->next->next로 업데이를 하게되는데 null->next라는 것은 존재할 수 없기 때문에 fast->next가 null인 경우도 고려해야한다. -
아래 그림에서 2. 는 cycle이 존재하는 경우를 보여주고 있다.
cycle이 존재한다면 cycle상에서 slow와 fast가 만나게 된다.
- method1: python3(hash set을 이용한 풀이)
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
nodes_seen = set()
while head is not None:
if head in nodes_seen:
return True
nodes_seen.add(head)
head = head.next
return False- mothod2: python3 & C++ (투포인터 fast slow이용)
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None:
return False
slow = head
fast = head.next
while slow != fast:
if fast is None or fast.next is None:
return False
slow = slow.next
fast = fast.next.next
return True파이썬 아래 코드도 됨.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None:
return False
slow = head
fast = head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if fast is slow:
return True
return FalseC++코드는 아래와 같다.
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL)
return false;
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow==fast)
return true;
}
return false;
}
};142. Linked list cycle 2
141번과 같은데, cycle이 있다면 cycle의 시작점도 return 해야 한다.
마찬가지로 Hash set또는 fast-slow pointer를 이용해 풀 수 있다.
-
hash set을 이용한 풀이는 141번 문제와 동일한 아이디어이다.
-
fast와 slow를 이용한 투포인터 문제는 다음과 같이 설명된다.
L1은 head부터 cycle의 entry까지의 길이
L2는 cycle의 entry부터 slow=fast인 지점까지의 길이
L3는 slow=fast인 지점부터 cycle의 entry까지의 길이(forward distance)
C는 cycle의 총 길이로 C = L2+L3
따라서 만약 fast와 slow 포인터로 fast==slow가 되는 지점을 찾았다면 head부터 시작하는 새로운 포인터와 slow포인터(fast==slow에 있는)를 동시에 같은 속도로 움직이면 두 포인터가 만나는 지점이 L1 = L3 + cycle루프를 만족하는 cycle의 시작점이 된다.
- method1 python3(hash set 이용)
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
visited = set()
while head is not None:
if head in visited:
return head
visited.add(head)
head = head.next
return None- mothod2 python3 & C++ (fast slow 투 포인터 이용)
파이썬 코드는 아래와 같다.
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return None
slow = head
fast = head
entry = head
while fast.next is not None and fast.next.next is not None:
slow = slow.next
fast = fast.next.next
if slow == fast:
while entry != slow:
entry = entry.next
slow = slow.next
return entry
return NoneC코드는 다음과 같다.
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL)
return NULL;
ListNode* slow = head;
ListNode* fast = head;
ListNode* entry = head;
while(fast->next != NULL && fast->next->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
while(entry != slow){
entry = entry->next;
slow = slow->next;
}
return entry;
}
}
return NULL;
}
};160. Intersection of Two Linked Lists
마찬가지로 1. hash set, 2. Two pointers 두가지 방법으로 해결할 수 있다.
1. python3 (hash set이용)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
visited = set()
pa = headA
pb = headB
while pa is not None:
visited.add(pa)
pa = pa.next
while pb is not None:
if pb in visited:
return pb
visited.add(pb)
pb = pb.next
return None- python3 (two-pointer 이용)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
pa = headA
pb = headB
while pa != pb:
pa = headB if pa is None else pa.next
pb = headA if pb is None else pb.next
return pa19. Remove Nth Node From End of List
singly linked list일때, 뒤에서 N번째 노드를 제거하는 문제이다.
two pointer를 사용하여 풀어본다.
- fast pointer를 미리 n번 앞쪽에다 놓은 뒤, fast와 slow를 같이 움직이면
- fast.next가 null이 될때의 slow는 제거하고자 하는 노드의 바로 앞전 노드를 가리키게 된다.
- linked list의 delete를 위해서는 제거하고자 하는 노드의 앞 노드를 알아야함에 유의.
- 예외케이스는 fast를 n번 움직였을 때 fast가 null이 되는 케이스인데, 이때 slow가 이미 삭제하고자 하는 노드(head node)를 가리키게 되고 이게 head이기 때문에 head = head.next로 head노드를 없애주면된다.
- python3 (two-pointer)
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
slow = fast = head
for _ in range(n):
fast = fast.next
if fast is None:
return head.next
while fast.next is not None:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return head