Linked List

Linked List는 상대적으로 쉬운편이다. Two-pointer technique를 참고하자. 행렬문제 뿐만 아니라, Linked List 문제에도 적용할 수 있다.

단순히 Linked list를 dummy node로 코딩하는 문제는 아래 예시와 같다.
ex. Reverse Linked List, Merge Two Sorted Lists, Linked List Cycle.

그리고, 좀 더 어려운 문로는 이 위의 문제들을 재귀적으로 푸는 Reverse Linked List, Palindrome Linked List and Merge Two Sorted Lists가 있다.

Two-pointer technique:

느린 선수와 또 다른 빠른 선수가 있다.
예를 들면, 하나의 포인터는 시작점에 있고, 다른 하나는 끝에서 시작한다.
두 개의 포인터는 서로의 방향으로 만날때 까지 이동한다.

Swap

private void swap(char[] str, int i, int j) {
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

Reverse

첫 번쨰 문자와 마지막 문자를 바꾸는 방법은 중간지점이 될때까지 반복적으로 바꾸는 것이다. 중간 점은 ⌊ 2/n ⌋ 이고, 홀수/짝수 크기의 행렬에서도 적용되는지 확인해야 한다.

public void reverse(char[] str) {
    int n = str.length;
    for (int i = 0; i < n / 2; i++) {
        swap(str, i, n - i - 1);
    }
}

Rever with Two Pointer

두 개의 포인터를 이용해서 문자를 뒤집는 경우가 있다. 이는, i++, j--를 하면서 중간 지점에서 만날때까지 실행한다.

public void reverse(char[] str) {
    int i = 0, j = str.length - 1;
    while (i < j) {
        swap(str, i, j);
        i++;
        j--;
    }
}

Reference

[1] https://leetcode.com/explore/interview/card/top-interview-questions-easy/93/linked-list/