linkedlist5 [Leetcode] 147. Insertion Sort List 문제 : https://leetcode.com/problems/insertion-sort-list/ 단일 linked list의 헤드가 주어질 때 삽입 정렬을 이용하여 이들을 정렬한뒤 정렬된 linked list의 헤드를 반환하라. 정렬된 링크드 리스트의 헤드를 저장하기 위해 ListNode를 하나 만들고 이 노드의 주소값을 newHead 변수에 저장한다. 원본 head의 노드를 처음부터 하나씩 정렬시켜야 하므로 앞에있는 노드부터 하나씩 탐색하며 newHead를 헤드로 하는 링크드 리스트의 적절한 위치에 연결해준다. 탐색하는 노드의 포인트를 originNode라 하자. 정렬된 링크드 리스트의 적절한 위치를 찾을 때 노드를 적절한 위치에 넣기 위해서는 해당 노드의 앞에 위치하는 노드를 알아야 한다. 예를 .. 2021. 12. 15. [Leetcode] 82. Remove Duplicates from Sorted List II 문제 : https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ 정렬된 linked list의 head 노드가 주어지면 중복된 번호를 가진 노드들은 모두 삭제하고 고유한 번호를 가진 노드들만 남겨라. head 노드의 앞에서부터 탐색하며 탐색중인 노드의 next 노드가 없거나 탐색중인 노드의 val 와 next 노드의 val이 다른경우 고유한 노드가 된다. 이 경우 탐색중인 노드는 삭제하지 않고 남겨야 하므로 별도의 ListNode 포인터 변수(let, prev)에 저장해둔다. prev->next에 현재 노드를 연결시켜준 뒤 prev도 탐색중인 노드로 갱신한다. 그리고 최초로 찾은 고유한 노드는 새로운 head 노드가 되므로 이를 또 다른.. 2021. 12. 3. [Leetcode] 61. Rotate List 문제 : https://leetcode.com/problems/rotate-list/ linked-list 의 head 노드가 주어지면 오른쪽으로 k만큼 회전한 뒤의 linked-list의 head를 반환하라. 입력으로 주어진 링크드 리스트를 한 번 탐색하면서 전체 길이를 구한다. (let, cnt) 만약 오른쪽으로 cnt번 회전하면 원래의 링크드 리스트와 동일해지므로, 나머지 연산을 한 k % cnt 만큼만 오른쪽 회전시키면 된다. 링크드 리스트를 다시 한 번 탐색하면서 o -> o -> o -> o -> o 만일 위와 같은 링크드 리스트가 있고 k가 2라면 빨간색 노드가 새로운 헤드 노드가 될 것이다. 즉, head노드의 cnt - k번째 next 노드가 헤드노드가 된다. 회전한 뒤의 모습은 원래 링.. 2021. 12. 2. [Leetcode] 203. Remove Linked List Elements 문제 : https://leetcode.com/problems/remove-linked-list-elements/ 링크드 리스트의 헤드와 정수값 val 이 주어지면 링크드 리스트들 중 노드 값이 val 과 같은 노드들은 제거한 뒤 헤드를 반환하라. head 부터 탐색하면서 만일 탐색 중인 노드 값이 val이 아니라면 다음 노드를 탐색한다. 만일 삭제해야 하는 노드라면 탐색 중인 노드의 바로 전 노드에 탐색 중인 노드의 next 노드를 연결한다. 이를 위해 최근에 탐색한 노드를 별도의 변수에 저장하고 있어야 한다. 만일 삭제될 노드가 head 노드라면 탐색중인 노드의 next 노드를 새로운 head 노드로 세팅한다. 시간복잡도는 O(N). N = 링크드 리스트 노드 개수. 소스코드 : https://git.. 2021. 11. 13. [leetcode] 1171. Remove Zero Sum Consecutive Nodes from Linked List 문제 : https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/ 링크드리스트 문제. 링크드리스트를 앞에서부터 탐색하면서 현재까지의 sum을 key, ListNode*을 value로 하는 map을 만들어서 저장해간다. 1, 3, 2, -3, -2, 5, 5, -5, 1 을 예로 들어보자. index 1 2 3 4 5 6 7 8 9 array 1 3 2 -3 -2 5 5 -5 1 subsum 1 4 6 3 1 6 11 6 7 합을 구하면 위 표와 같다. 링크드리스트라 인덱스로 표현되지는 않지만 말하기 쉽게 임의로 차례대로 인덱스를 붙여놓았다. 1. subsum으로 검색시 map에 없는 경우 인덱스 1~4가 이에 속한다.. 2019. 8. 28. 이전 1 다음