..

Linked List, Middle of the Linked List

Problem

876. Middle of the Linked List

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Constraints:

  • The number of nodes in the list is in the range [1, 100].
  • 1 <= Node.val <= 100

문제 해석

주어진 연결리스트의 중간 노드 포인터를 반환해야 한다. 만약, 짝수개의 연결리스트의 경우 중간에서 두 번째의 노드 포인터를 반환한다.

My Approach

시도

쉽게 생각해보면 Iteration을 2번 돌면 된다 (Bruth force) for문 내부에서 while문을 돌면서 next pointer를 계속 따라가면서 사이즈를 먼저 측정한다.

Q) Singly Linked list의 중간을 어떻게 알 수 있지?

  • 워커/러너 테크닉

Q) Linked list에서 다음 노드로 가는 액션?

  • runner = runner.next

해당 문제에 접근할 수 있는 네 가지 방법이 있다

완전 탐색 Brute force approach using extra memory

기본 아이디어는 각 연결리스트 노드를 저장한다. 연결리스트와 같은 사이즈의 추가 리스트를 사용한다. 추가 리스트의 중간 인덱스에 접근해서 중간 노드를 가져올 수 있다.

class Solution {
	public ListNode middleNode(ListNode head) {
		int len = listLength(head);
		List<ListNode> temp = Array.asList(new ListNode[len]);
		int count = 0;
		while(head != null){
			temp[count] = head;
			count += 1;
			head = head.next;
		}
		return temp[count / 2];
	}

	// Linkedlist 사이즈 측정 메서드
	public int listLength(ListNode head){
		int len = 0;
		while (head != null){
			len += 1;
			head = head.next;
		}
		return len;
	}

}

Time Complexity

  • finding length of the linked list + storing nodes in extra memory = O(n) + O(n) = O(n)

Space Complexity

  • O(n), for storing nodes in an n-size array

이중 순회 Double traversal of the linked list

첫 번째 순회에서 노드의 개수(count)를 센다. 그리고 두 번째 순회에서 count/2 만큼만 연결리스트를 순회한다.

class Solution {
	public ListNode middleNode(ListNode head) {
		int count = 0;
		ListNode middle = head;

		while(head != null){
			count += 1;
			head = head.next;
		}

		int idx = 0;
		while(idx < count/2){
			middle = middle.next;
			idx += 1;
		}

		return middle;
	}
}

Time Complexity - O(n) Space Complexity - O(1) for using constant extra space

단일 순회 Single traversal of the linked list

노드의 개수와 중간 노드를 동시에 파악 할 수 있다. head는 매번 앞으로 나아가고 middle은 루프순회 2번에 한번만 나아간다. head가 null일때 middle의 위치는 중간 노드이다.

class Solution {
	public ListNode middleNode(ListNode head) {
		int count = 0;
		ListNode middle = head;
		while(head.next != null){
			
			if(count % 2 == 0){
				middle = middle.next;
			}
			count += 1;
			head = head.next;
		}
	}
}

Time Complexity - O(n) for constant operations

Space Complexity - O(1) as using constant extra space

워커 러너 Walker and runner pointers

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/

class Solution {
	public ListNode middleNode(ListNode head) {
		ListNode walker = head;
		ListNode runner = head;
	
		while(runner != null){
			runner = runner.next
			if(runner != null){
				walker = walker.next;
				runner = runner.next;
			}
		}
		return walker;
	}

	// same function
	public ListNode findMiddleLinkedList(ListNode head){
		ListNode fast = head;
		ListNode slow = head;
		while (fast != null && fast.next != null){
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
}

time complexity

  • walker and runner are running n/2 number of steps doing O(1) operation
  • n/2 * O(1) = O(n)

space complexity

  • using constant extra space
  • thus O(1)