Reverse Linked List II

92. Reverse Linked List II

문제 설명

연결 리스트의 head와 두 정수 left와 right가 주어질 때(left <= right), left부터 right까지 노드들을 뒤집고, 연결리스트를 리턴하라.

해결 방법

변하지 않는 start(left의 한칸 앞)와 end(left 노드) 노드를 두고, start와 end 사이로 범위에 있는 노드들을 하나 씩 넣는다.

1. 먼저 left가 0이 아닌 1부터 시작하기 때문에 root노드를 하나 만들어서 head 앞에 연결한다.
2. left - 1에 start 노드를 위치시키고, start.next에 end를 위치시킨다.
3. end.next를 임시 변수(tmp)에 할당하고, end.next를 tmp.next로 변경
4. tmp.next를 start.next로 변경
5. start.next를 tmp로 변경
6. 위 과정을 끝까지 반복한다.

풀이 코드

function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  if (!head || left === right) return head;

  const root = new ListNode(0, head);
  let start = root;
  for (let i = 0; i < left - 1; i++) {
    start = start.next;
  }
  const end = start.next;

  for (let i = 0; i < right - left; i++) {
    const tmp = end.next;
    end.next = tmp.next;
    tmp.next = start.next;
    start.next = tmp;
  }

  return root.next;
}

테스트 코드

describe(' description', () => {
  test('example test 1', () => {
    const input = convertArrayToList([1, 2, 3, 4, 5]);
    const output = reverseBetween(input, 2, 4);
    const expected = convertArrayToList([1, 4, 3, 2, 5]);
    expect(output).toEqual(expected);
  });

  test('example test 2', () => {
    const input = convertArrayToList([5]);
    const output = reverseBetween(input, 1, 1);
    const expected = convertArrayToList([5]);
    expect(output).toEqual(expected);
  });
});