Reverse Linked List II

문제: https://leetcode.com/problems/reverse-linked-list-ii/

linkedList : node 가 주어졌을 때 m,n사이의 linkedList만 뒤집는 문제이다.

이 문제를 푸는 것은 어렵지 않을 수 있다. 배열로 값들을 갖고와서 그 부분만 reverse해서 linkedList로 만들면 된다.

하지만 새로운 ListNode 객체를 만들어서 붙이는 건 별로인 풀이라고 생각된다.

현재 객체의 next를 변형시키는 것이 이 문제의 주된 목적이라고 생각한다. 근데 너무 어려워서 책보고 이해하는데도 한참이 걸렸다.

해결방법

start: reverse가 시작되기 직전 node
end : 초기 start.next 종료시점에 end뒤에는 reverse가 되지 않는 node들이 오게 된다.
start 와 end는 변경되지 않는다. (next부분만 수정해서 순서를 변경시킨다.)

위의 start, end 세팅이 완료 되면 아래의 반복을 m~n까지 시작한다.

tmp = start.next;
start.next = end.next;
end.next = end.next.next;
start.next.next = tmp;

예시로 시도해보자.
ex) 1-2-3-4-5

1. tmp: [2,3,4,5]
   start: [1,3,4,5]
   end: [2,4,5]
   start: [1,3,2,4,5]
2. tmp: [3,2,4,5]
   start: [1,4,5]
   end: [2,5]
   start: [1,4,3,2,5]

내가 위의 코드를 보고 처음에 이해가 안되는 부분이 있었다.

start.next.next = tmp를 할 때 tmp가 [2,3,4,5]인데 중간에 있던 3은 없어지고 왜 [1,3,2,4,5]로 변할까라고 생각 됐다.

• end.next=end.next.next 구문에서 tmp를 변경시키는 것이었다.
  1단계
  end.next=end.next.next이 부분에서 end:[2,3,4,5] => end:[2,4,5] 로 되면서 tmp: [2,3,4,5] => tmp:[2,4,5]로 변하게 된다.

• 2단계
  tmp:[3,2,4,5] 가 end.next=end.next.next를 거치면 end:[2,4,5] => end:[2,5] 가 되면서 tmp: [3,2,4,5] => tmp:[3,2,5] 가 되고 start : [1,4,3,2,5] 가 되는 것이다.

---

즉,
tmp=start.next - temp를 이용해 start 다음 부분 재정렬하기 위해
start.next = end.next - start 바로 뒤를 end 뒤에 있는 수로 설정
end.next = end.next.next - start뒤에 설정된 end.next를 next.next로 변경
start.next.next = tmp - start는 start - end.next - tmp 로 설정된다.
위의 4과정을 다바꿀 때 까지 반복한다.

---

code

const reverseBetween = (node, m, n) => {
  if (!node || m === n) return node;

  const head = new ListNode();
  let start = head;
  head.next = node;

  for (let i = 1; i < m; i++) {
    start = start.next;
  }
  let end = start.next;
  let tmp = null;

  for (let i = m; i < n; i++) {
    tmp = start.next;
    start.next = end.next;
    end.next = end.next.next;
    start.next.next = tmp;
  }
  return head.next;
};

마무리

사실 말로도 잘 설명 못하겠다. tmp안에 end가 들어있어서 end가 변경되면 tmp로 변경되는... 이런걸 어떻게 계산하고 코드를 짜는지 모르겠다.
배열로 바꿔서 풀면 쉽긴 하겠지만 책에서 말에 따르면 인터뷰에서는 그렇게 얘기하면 기대하는 방향이 아니기 때문에 위와 같이 링크드리스트를 조작하는 방법으로 해결하는게 좋다고 한다.
배열과 다르게 next를 변경함에 따라서 그 노드가 들어있는 다른 모든 것까지 변경이 되니까 더더 헷갈리는 것 같다.

참조

• 책: 파이썬 알고리즘 인터뷰