본문 바로가기

Coding Test/LinkedList

 (5)
[Leetcode] 328번 - 홀짝 연결 리스트 1. 문제 파악문제 링크: https://leetcode.com/problems/odd-even-linked-list/description/문제 정의: 홀수 인덱스인 노드끼리 연결하고 짝수 인덱스이 노드끼리 연결해라. (첫번째 노드부터 인덱스가 홀수로 시작한다.)문제의 제약 파악 (입력값 크기, 상수 조건)입력 크기: 0 ~ 10000시간 복잡도: O(N)추가 공간 복잡도: O(1)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일단, 추가 공간 복잡도가 O(1)으로 제한되어있기 때문에 새로운 연결리스트를 생성하는 것이 아니고, 기존의 연결리스트에서 참조값 변경을 통해 재구조화 시키는 것이다. 문제를 풀기 위해서는 크게 다음 3개의 단계를 거쳐야한..
[Leetcode] 24번 - 페어의 노드 스왑 1. 문제 파악문제 링크: https://leetcode.com/problems/swap-nodes-in-pairs/description/문제 정의: 연결리스트에서 노드 쌍의 순서를 변경해라.문제의 제약 파악 (입력값 크기, 상수 조건): 시간복잡도 O(N)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악)해당 문제는 연결리스트를 순회하면서 노드간에 참조를 변경해야한다. 참조 값의 수정을 통해 연결리스트를 재구구조화하는 문제이다.연결리스트에서 노드 두개의 쌍끼리의 위치를 변경해야한다.first step: 첫번재 노드와 두번째 노드의 위치를 변경한다.second step: 세번째 노드와 네번째 노드의 위치를 변경한다.input: 1 2 3 4output: 2 1 4 31 2 3 4 // origi..
[Leetcode] 2번 - 두 수의 합 1. 문제 파악문제 링크: https://leetcode.com/problems/two-sum/description/문제 정의: 주어진 두 연결리스트의 각 노드에 저장된 숫자를 더해서 새로운 연결리스트를 생성해라.문제 주의점:주어진 두 연결리스트의 노드 개수가 다를 수 있다.두 개의 노드의 수를 저장한 값이 올림수가 있을경우, 주어진 연결리스트보다 노드 개수가 많은 연결리스트가 생성될수있다.시간복잡도: O(N)2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악)일단, 두개의 연결리스트를 순차적으로 노드를 순회하면서 덧셈을 진행하면 된다. 이렇게 덧셈을 진행해서 반환을 위한 새로운 연결리스트가 완성될때까지 반복문을 수행한다. 하지만, 위의 문제 주의점에서 두개의 조건에 따라 반복문 탈출조건을 설정해야..
[Leetcode] 19번 - Remove Nth Node From End of List 1. 문제 파악문제 링크: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/문제: 마지막 노드로부터 n번째 노드를 삭제하고 head를 반환해라.시간복잡도 파악: 연결리스트의 입력 크기가 30이라서 O(N) 이내어야한다. 2. 입출력 케이스 도출일반 케이스: head = [1,2,3,4,5], n = 2 -> [1,2,3,5], head = [1,2], n = 1 -> [1]엣지 케이스: head = [1], n = 1 -> [], head = [1,2], n = 2 -> [2] 3. 핵심 문제 풀이 도출연결리스트의 끝에서 n번째 노드를 삭제하는 것이다. 그래서 나는 스택 자료구조가 떠올랐다. 스택에 연결리스트 노드를..
[Leetcode] 143번 - Reorder List 1. 문제 파악문제 링크: https://leetcode.com/problems/reorder-list/문제: L0 → L1 → … → Ln - 1 → Ln 수열인 연결 리스트를 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …로 재정렬해라.시간복잡도 파악: 입력크기가 50000이라서 O(nlogn) 이내어야한다. 2. 입출력 케이스 도출짝수: [1 2 3 4]홀수: [1], [1 2 3 4 5 6 7] 3. 핵심 문제 풀이 도출 양쪽 끝 투 포인터(left, right) 사용해서 연결 리스트를 재정렬할수있다. 여기서 left와 right는 기존 리스트의 노드 순서를 가리킨다.EX1) [1, 2, 3, 4][1, 2, 3, 4]: left = L1, right = L4Logic: ..

티스토리툴바