# Two Pointers
- Two pointers 알고리즘은 Array 나 Linked List 와 같은 linear 자료구조에서 부분 수열 (subsequence)에 대한 정보를 가져올 때, $O(N^2)$이 아니라 $O(N)$ 의 시간복잡도로 가져올 수 있는 방법으로 사용이 된다.
- 구성은 $start$ 와 $end$ 이렇게 2개의 포인터를 사용하고, $start \leq end$ 라고 가정한다.
- '슬라이딩 윈도우'라고 불리는 방법은 Two pointer 알고리즘을 사용하고, 윈도우의 크기가 어느 지점에서 일정하다고 간주한다.
- Two pointer를 사용하는 방법에는 2가지가 있다.
1. $start$ 와 $end$가 시작과 끝에서 움직이면서 서로 만날 때까지 이동하는 방법.
2. $start$ 와 $end$가 하나는 더 빨리 이동하고 (at a faster pace), 다른 하나는 뒤를 따라가는 (at a slower pace) 방법.

Reverse Array (In-place)
---
- Array를 in-place 방법으로 reverse 하는 방법
- 제일 첫번째 아이템과 마지막 아이템을 swap. 그 다음 아이템과 그 다음 마지막 아이템을 swap. 반복

def reverse(self, nums, start, end):
    while start < end:
        nums[start], nums[end] = nums[end], nums[start]
        start, end = start + 1, end - 1

- 문제: https://leetcode.com/problems/reverse-string/

Rotate Array (In-place)
---
- Array 가 주어졌을 때 1 step 순환시키는 방법은 데이터들이 한칸씩 자리를 이동하는 것을 의미한다. K step 은 이 작업을 여러번 수행하는 것이다.
- 단순한 방법으로는 추가적인 배열을 만들어서 1 step 이동시킨 값을 저장하는 것이지만, 이 방법은 $O(N^2)$ 만큼의 시간복잡도와 추가적인 공간이 필요하다.
- 만약에 two pointer를 사용한다면
- 왼쪽으로 Rotate 할 때,
1) 0 ~ end-k 까지 reverse
2) 0 ~ end-k+1 까지 reverse
3) 0 ~ end 까지 reverse 를 하면 step 만큼 rotate를 할 수 있다.
- 오른쪽으로 Rotate 할 때 반대로 한다.
1) 0 ~ end 까지 reverse 를 하면 step
2) 0 ~ end-k+1 까지 reverse
3) 0 ~ end-k 까지 reverse
- 문제: https://leetcode.com/problems/rotate-array/

class Solution:
    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start, end = start + 1, end - 1
        
    def rotateLeft(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if k is None or k <= 0:
            return
        
        k, end = k % len(nums), len(nums) - 1
        self.reverse(nums, 0, end - k)
        self.reverse(nums, end - k + 1, end)
        self.reverse(nums, 0, end)

- 문제: https://leetcode.com/problems/rotate-array/

연속적인 수열의 합
---
- 전체 데이터에서 연속적인 수열의 부분합이 target 값 $T$를 만족하는지 알아보는 문제다.
- 가장 단순한 방법으로는 가능한 모든 연속적인 수열을 찾으면서 그 합을 $T$와 비교하는 방법이 있는데, 이것은 시간복잡도가 $O(N^2)$이 걸린다.
- Two pointer 방법을 사용하면 이 시간복잡도를 $O(N)$으로 줄일 수 있다. 현재까지의 수열의 합이 $T$ 보다 작으면 $end$ 포인터를 하나 증가시키고, 부분합에 $end$가 가리키는 값을 누적시킨다. 만약에 $T$보다 크면 $start$ 포인터를 하나 증가시키고, 부분합에서 $start$ 위치에 있던 값을 뺀다. 이런 방식으로 $start$와 $end$ 의 위치를 조절하면 $O(N)$ 시간 안에 답을 찾을 수 있다.

Linked List의 중간값 찾기
---
- Array의 경우에는 중간값을 찾는 방법은 중간 인덱스를 찾을 수 있다. 하지만 Singly Linked List 의 경우 전체 리스트의 길이를 모른다고 가정할 때 어떻게 하면 중간값을 찾을 수 있을까?
- 가장 단순한 방법은 $O(N)$의 시간을 소비해서 Linked List의 크기를 알아보고, 다시 한 번, 리스트를 탐색하면서 중간값을 찾을 수 있다.
- 하지만, Two pointer를 사용해서 $slowPointer$는 하나의 step을 증가시키고, 다른 하나의 포인터인 $fastPointer$는 두개의 step을 증가시킨다. 이렇게 되면 $fastPointer$가 가장 마지막 위치에 도달했을 때, $slowPointer$는 중간 위치에 도달하기 때문에 중간값을 전체 크기를 모른 상태에서도 알 수 있다.

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
return slow

Reverse Linked List
---
- Doubly Linked List를 사용하지 않고 Singly Linked List 를 반대로 traverse하는 방법이 있을까?
1. Three pointers를 사용하는 방법
2. Two pointers를 사용하는 방법

#### Three pointers를 사용하는 방법
- Two pointers 를 사용하는 방법을 보기 전에 three pointers를 사용하는 방법을 먼저 보자. 노드를 traverse하면서 노드의 next를 prev로 업데이트하는 과정을 반복한다. 여기서는 추가적으로 3개의 포인터를 사용해서 reverse할 수 있다.
- $prev$: 이전 노드를 가리키는 포인터
- $next$: 다음 노드를 가리키는 포인터
- $curr$: 현재 노드를 가리키는 포인터
> $head$ 는 기존에 사용하고 있는 포인터이기 때문에 three pointers 라고 부른다.
- $curr$ 노드를 $next$ 노드로 업데이트 하기 전에 $curr$ 의 next 가 $prev$ 를 가리키도록 한다.
- $prev$ 는 $curr$ 로 업데이트 한다.
- $curr$ 를 $next$ 로 업데이트 한다
- $next$ 를 $curr$ 의 next로 업데이트 한다.

#### Two pointers를 사용하는 방법
- Two pointers 로는 $curr$ 와 $next$ 포인터만 갖고 reverse 할 수 있다.
- $next$: 다음 노드를 가리키는 포인터
- $curr$: 현재 노드를 가리키는 포인터
- $head$ 와 $curr$ 는 같이 이동한다고 생각한다.
- $curr$의 next를 $next$ 의 next 로 업데이트 한다.
- $next$의 next를 $curr$ 로 업데이트 한다.
- $head$ ($curr$) 를 $next$로 업데이트 한다.
- 한 번 반복을 하면, $next$의 next는 $curr$를 가리키게 되고, $curr$ 와 $next$ 는 다음 노드로 한 칸 이동시키는 효과가 있다. 코드를 보면 다음과 같다.

# 출처: https://www.geeksforgeeks.org/iteratively-reverse-a-linked-list-using-only-2-pointers/?ref=lbp
# Function to reverse the linked list using 2 pointers
def reverse(head_ref):
 
    current = head_ref
    next= None
    while (current.next != None) :
        next = current.next
        current.next = next.next
        next.next = (head_ref)
        head_ref = next
     
    return head_ref

- 문제: https://leetcode.com/problems/rotate-array/

Rotate Linked List
---
- Left 로 Rotate 하는 것은 별로 어렵지 않고, Right 로 Rotate 하는 것도 move 하는 값만 조금 조정하면 된다.

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return None
        
        p = head
        size = 1
        while p.next:
            size +=1
            p = p.next
        p.next = head     
        k %= size
        
        for i in range(size-k-1):
            head = head.next
        ans = head.next 
        head.next = None
        return ans

- 문제: https://leetcode.com/problems/rotate-list/

참고 자료
---
1. https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md
2. https://guides.codepath.com/compsci/Linked-List-Two-Pointer
3. https://leetcode.com/articles/two-pointer-technique/
4. https://www.baeldung.com/java-two-pointer-technique