런너기법이란?

런너기법이란 연결리스트를 순회하며 두개의 포인터를 사용하는 기법이다. "부가 포인터"라고도 한다.
연결리스트에서 주로 사용되며 연결리스틑 순회할때 두개의 포인터를 사용하는 방법이다. 하나의 포인터는 빠르게 증가하고 하나의 포인터는 느리게 증가하여 병합지점, 중간지점 ,길이등을 판별할때 유용하다.

예를들어,
fast포인터는 2*i씩 증가하고 느린포인터는 i씩 증가한다면, fast포인터가 끝에 도달했을때 slow포인터는 중간 지점에 있게된다.
다시 fast포인터를 기본 리스트로 초기화하고 slow.next에 별도의 변수에 할당한뒤(참조값 유지) slow.next를 null로 설정하면 fast와의 연결점이 끊어짐으로서 한개의 연결리스트가 두개의 리스트로 분할된다.

function patition(head) {
  let fast = head;
  let slow = head;
  while (fast.next !== null && fast.next.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let left = head;
  let right = slow.next;

  slow.next = null;
 
 return [left ,right]
}

주의

짝수와 홀수일때를 구분해야한다.
짝수일때는 slow.next를 분리점으로 한다면 2등분이 가능하나, 홀수일 경우 slow가 가리키는 지점이 중앙지점이 된다.
만약 Palindrome 문제를 푼다면 가운데 요소는 필요가 없다. 이럴때, slow 해당 값을 버린다고 생각하면된다.

해결할 문제

1. 루프를 돌릴때 , fast.next & fast.next.next만 비교하는 경우가 많던데 fast는 비교를 안해도되는가? undefined오류가 떨어질 것이라고 생각하는데 이점에 대해 의문이 남는다.
   해결: 이미 while문의 조건으로 fast.next.next가 null이 아님을 확인했으므로 fast.next.next를 할당받은 fast는 null이 될 수 없다!