연결리스트 중앙값 찾기

개요

1->2->3->4->5->6->7의 연결리스트가 주어진다면 4를 반환하는 문제이다.

만약 1->2->3->4->5->6처럼 개수가 짝수라면 3 또는 4를 반환하면 된다.

면접하는 도중에 풀이법을 떠올리려니 쉽지 않았다.

가장 간단하게 전체 리스트를 순회하여 리스트의 길이를 구하고 해당 값의 절반만 순회하여 값을 반환하는 방식으로 구현했다.

하지만 이 경우 시간복잡도가 O(2n) 이므로 효율적이지 못하다.

결국에 더 효율적인 방법을 찾지못해서 다음 문제로 넘어가고 말았다.

이제 가장 간단한 방법부터 더욱 효율적인 방법을 설명하고자 한다.

1. 전체순회

앞서 설명한 것 처럼 전체 노드를 순회하며 count를 누적시킨다. 만약 next가 null이라면 순회를 종료하여 전체 길이를 구한다. 전체 길이의 절반을 다시 순회하여 중간값을 찾고 반환한다.

2. 포인터 2개 사용

진행 속도가 다른 두 개의 포인터를 사용하여 중앙값을 구한다.

속도가 빠른 포인터는 2칸씩 이동하고 속도가 느린 포인터는 1칸씩 이동한다.

속도가 빠른 포인터가 더 이상 진행할 수 없을 때 속도가 느린 포인터의 값을 출력하면 된다.

이 경우 1번 방법처럼 다시 순회할 필요가 없어 시간복잡도가 개선된다.

# Node class
class Node:

	# 노드 오브젝트 초기화 함수
	def __init__(self, data):
		self.data = data 
		self.next = None 

class LinkedList:

	def __init__(self):
		self.head = None

	# 새로운 노드를 head로 지정
	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# 연결 리스트 출력
	def printList(self):
		node = self.head
		while node:
			print(str(node.data) + "->", end="")
			node = node.next
		print("NULL")

	# 중앙값 출력 함수
	def printMiddle(self):
		# slow -> 1칸씩 이동, fast -> 2칸씩 이동
		slow = self.head
		fast = self.head

		# fast가 끝까지 도달할때 까지 이동
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		
		# 중앙값 출력
		print("The middle element is ", slow.data)

if __name__=='__main__':

	# Start with the empty list
	llist = LinkedList()

	for i in range(5, 0, -1):
		llist.push(i)
		llist.printList()
		llist.printMiddle()

# Code is contributed by Kumar Shivam (kshivi99)

아래의 이미지를 보면 이해하기가 수월하다.

3. count 절반만 하기

위의 두개의 포인터 사용과 비슷하다. 2번과 비슷하지만 하나의 포인터가 한칸 씩 이동하며 짝수번째 이동일 때 마다 mid 포인터를 이동시키는 방법이다. 생각해보면 2번과 동일하다.

# Node class
class Node:
	
	# Function to initialise the node object
	def __init__(self, data):
		self.data = data # Assign data
		self.next = None # Initialize next as null
	
# Linked List class contains a Node object
class LinkedList:
	
	# Function to initialize head
	def __init__(self):
		self.head = None

	# Function to insert a new node at the beginning
	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# Print the linked list
	def printList(self):
		node = self.head
		while node:
			print(str(node.data) + "->", end = "")
			node = node.next
		print("NULL")

	# Function to get the middle of
	# the linked list
	def printMiddle(self):
		count = 0
		mid = self.head
		heads = self.head

		while(heads != None):
	
		# Update mid, when 'count'
		# is odd number
			if count&1:
				mid = mid.next
			count += 1
			heads = heads.next
			
		# If empty list is provided
		if mid!=None:
			print("The middle element is ", mid.data)

# Code execution starts here
if __name__=='__main__':
	
	# Start with the empty list
	llist = LinkedList()
	
	for i in range(5, 0, -1):
		llist.push(i)
		llist.printList()
		llist.printMiddle()

# This Code is contributed by Manisha_Ediga

출처 : https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/