[2.연결리스트] 중복없애기, 뒤에서 k번째 원소구하기, 중간노드삭제, 분할, 리스트의합, 회문(연결리스트), 교집합, 루프발견

 [ Q1. 중복없애기 ] 

정렬되어있지 않은 연결리스트가 주어졌을때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라.

(임시버퍼가 없다면 어떻게 풀까?)

 

- 내 풀이 -

1. 해시맵 활용(연결리스트 저장용도)

2. 연결리스트를 순회하며 n이 키로 존재하는지 체크

=> 존재하지 않는 경우 맵에 <n, n.next>를 삽입

=> 존재하는 경우 n.prev.next=n.next로 변경 (이게 노드 삭제)

* 야 내 문제는 노드클래스 구현하는거가 문제야..

class LinkedNode{
	int data;
	LinkedNode prev, next;
	
	public LinkedNode() {
		// TODO Auto-generated constructor stub
	}
	public LinkedNode(int d) {
		data=d;
	}
	
}

void removeDups(LinkedNode head) {
	LinkedNode n=head;
	HashMap<Integer, LinkedNode> map=new HashMap<Integer, LinkedNode>();
	while (n.next!=null) {
		int key=n.data;
		if(map.containsKey(key)) {
			n.prev.next=n.next;
		} else {
			map.put(key, n.next);
		}
		n=n.next;
	}

 

- 모범답안 - 

연결리스트의 중복되는 원소를 제거하기위해서 원소를 추적해야함 : 해시테이블 사용

해법1) 단순히 연결리스트를 순회하며 각 원소를 해시테이블에 저장 > 중복원소 발견시 그 원소 제거하고 진행

(연결리스트를 사용하고있기때문에 한번에 순회로 전부 처리 가능 - O(N)의 시간 소요)

*내가 구현한 것과 동일한데 해법에서는 set구조를 사용하고있고, Node클래스 구현하는 방법에서 차이가 있음

class LinkedListNode{
	public LinkedListNode next, prev, last;
	public int data;

	public LinkedListNode() {
		// TODO Auto-generated constructor stub
	}
	public LinkedListNode(int d) {
		data=d;
	}
	public LinkedListNode(int d, LinkedListNode n, LinkedListNode p) {
		data=d;
		setNext(n);
		setPrevious(p);
	}
	
	public void setNext(LinkedListNode n) {
		next=n;
		if(this==last) {
			last=n;
		}
		// 다음 노드가 null이 아니고, 다음노드의 prev(this여야함)가 this가 아닌경우
		if(n!=null&&n.prev!=this) {
			// 다음노드의 prev를 현재노드로 변경
			n.setPrevious(this);
		}
	}
	public void setPrevious(LinkedListNode p) {
		prev=p;
		if(p!=null&&p.next!=this) {
			p.setNext(this);
		}
	}
}

void deleteDups(LinkedListNode n) {
	HashSet set=new HashSet();
	LinkedListNode previous=null;
	while(n!=null) {
		if(set.contains(n.data)) {
			previous.next=n.next;
		} else {
			set.add(n.data);
			previous=n;
		}
		n=n.next;
	}
}

 

"연관: 임시버퍼가 없다면 어떻게 풀까?"

해법2) 버퍼가없다면 2개의 포인터를 사용하여 문제를 해결

=> current포인터 : 연결리스트를 순회

=> runner포인터 : 뒤에 중복원소가 있는지를 확인

(이 경우 공간은 O(1)을 사용하지만 수행시간은 O(N^2) 소요)

void delDups(LinkedListNode head) {
	LinkedListNode current=head; // 순회할 포인터
	while (current!=null) {
		// 값이 같은 노드를 모두 제거 : runner포인터 이용
		LinkedListNode runner=current;
		while(runner.next!=null) {
			if(runner.next.data==current.data) {
				runner.next=runner.next.next;
			} else {
				runner=runner.next;
			}
		}
		current=current.next;
	}
}

 

 

 [ Q2. 뒤에서 k번째 원소구하기 ] 

단방향 연결리스트가 주어진 경우, 뒤에서 k번째 원소를 찾는 알고리즘을 구하라.

 

- 내 풀이 -

총 사이즈를 안다면 Length-k번째 원소까지만 차례로 순회하면 된다.

즉, 2번 순회하게됨 비효율적..

class Node {
	int data;
	Node next;
	public Node() {
		// TODO Auto-generated constructor stub
	}
	public Node(int d) {
		data=d;
	}
}
Node findKfromLast(Node n, int k) {
	// 길이-k만큼 순회하면 값을 찾을 수 있음
	for(int i=0; i<sizeNode(n)-k+1; i++) {
		n=n.next;
	}
	return n;
}

// 길이를 알기위해서 순회해야함
int sizeNode(Node n) {
	Node node=n;
	int size=1;
	while(node.next!=null) {
		size++;
	}
	return size;
}

 

- 모범답안 - 

이 문제를 비재귀와 재귀방식 2가지로 풀이

재귀알고리즘은 깔끔(코드는 짧지만)하지만 최적이 아닌 경우(이 문제의 경우 공간복잡도가 O(n))가 많다.

 

해법1) 연결리스트의 길이를 아는 경우

맨 마지막 원소에서 k번째 원소 = length-k번째 원소 

단순하게 연결리스트를 순회해서 푸는 것이기 때문에 분명 이렇게 푸는것을 권장하지 않는다!

 

해법2) 재귀적 방법 : 연결리스트를 재귀적으로 순회

마지막 원소를 만나면 0으로 설정된 카운터 값을 반환 >> 재귀적으로 호출된 부모메소드는 카운터에 1을 더함

>> 카운터가 k가 되는 순간 = 뒤에서 k번째 원소에 도달한 것

(스택을 통해 정수값을 전달하는 방법도 있지만 노드와 카운터값을 동시에 반환할 수 없어...ㅠ_ㅠ)

그렇다면?

[방법1] 원소를 반환하지 않는다.

문제를 수정하여 k번째 원소값을 출력만 하는것으로 대체 > 카운터값만 반환

	int printKthToLast(LinkedListNode head, int k) {
		if(head == null) {
			return 0;
		}
		int index=printKthToLast(head.next, k)+1;
		if(index==k) {
			System.out.println(k+"th to last node is "+head.data);
		}
		return index;
	}

[방법2] Wrapper 클래스 사용

위 방법1처럼 카운터와 첨자를 동시에 반환할 수 없는것이 문제인 경우

카운터값을 클래스로 감싸면(혹은 원소가 딱 하나인 배열사용) 참조에의한 값 전달 임시적으로 가능

	class Index {
		public int value=0;
	}
	
	LinkedListNode kthToLast(LinkedListNode head, int k) {
		Index idx=new Index();
		return kthToLast(head, k, idx);
	}
	LinkedListNode kthToLast(LinkedListNode head, int k, Index idx) {
		if(head==null) {
			return null;
		}
		LinkedListNode node=kthToLast(head.next, k, idx);
		idx.value=idx.value+1;
		if(idx.value==k) {
			return head;
		}
		return node;
	}

해법 3) 순환적 방법

두개의 포인터를 사용하여 두 간격을 k로 둔 후 동시에 이동 > 마지막에 다다른 경우 앞선 포인터의 위치가 k

	LinkedListNode nthToLast(LinkedListNode head, int k) {
		LinkedListNode p1=head;
		LinkedListNode p2=head;
		
		// p1을 k노드만큼 이동
		for(int i=0;i<k;i++) {
			if(p1==null) return null;
			p1=p1.next;
		}
		
		//p1과p2를 함께 움직임 > 이때 p1이 마지막에 도달했을때의 p2값
		while(p1!=null) {
			p1=p1.next;
			p2=p2.next;
		}
		return p2;
	}

 

 

 

 [ Q3. 중간 노드 삭제 ] 

단방향 연결리스트가 주어진 경우 중간(정확히 가운데일 필요는 없고 처음과 끝노드만 아니면 된다)에 있는 노드 하나를 삭제하는 알고리즘을 구현라하. 단 삭제할 수 있는 노드에만 접근가능하다.

예제

입력 : 연결리스트 a>b>c>d>e에서 노드 c

결과 : 아무것도 반환할 필요는 없지만, 결과로 연결리스트는 a>b>d>e가 되어있어야 한다.

 

- 내 풀이 -

제거노드를 n이라고 가정할때 n.prev.next=n.next로 변경해주면 OK

void deleteNode(LinkedListNode target) {
	if (target.prev!=null && target.next!=null) {
		target.prev.next=target.next;
	}
}

 

- 모범답안 -

이 문제는 연결리스트의 헤드에 접근할 수 없고 삭제노드만 접근할 수 있다는 것이 핵심

삭제를원하는 노드의 다음노드 데이터를 연재노드에 복사 후 다음 노드 삭제하는 방법 사용

boolean deleteNode(LinkedListNode n) {
	if(n==null || n.next==null) {
		return false;
	}
	LinkedListNode next=n.next;
	n.data=next.data;
	n.next=next.next;
	return true;
}

 

 

 [ Q4. 분할 ] 

값 x가 주어졌을때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에오도록하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 그보다 작은 원소들보다 뒤에 나오기만 하면된다. 즉 원소 x는 '오른쪽그룹' 어딘가에만 존재하면 된다. 왼쪽과 오른쪽 그룹사이에 있을 필요는 없다.

예제

입력 : 3>5>8>5>10>2>1 [분할값 : 5]

출력: 3>1>2>10>5>5>8

- 내 풀이 -

분할값x와 노드 data를 비교 > 크거나 같으면 그 자리에 둠, 작으면 맨 앞으로 위치시키기

그러나.. 위치 변경시 head와 node의 기준점이 헷갈려서 풀지못했다...^^

=> 해법2를 보고 next노드를 먼저 분리해 저장해두면 가능할 줄 알았는데, 나는 큰 노드를 만났을때 움직이지 않고 제자리를 지키는 것으로 구상했더니 이러면 노드가 끊어짐 > 그래서 해법2에서 큰수는 뒤에 붙이기를 한 것!

 

 

- 모범답안 -

배열에서 원소이동 비용은 비싸다 > 하지만 연결리스트로는 조금 더 쉽게 구현 가능

해법1) 원소의 값을 이동(shift)하고 바꾸는(swap)대신 서로 다른 연결리스트 두개를 만들면됨

=> 이 방법은 분할 작업을 할 때 원소이동이 없고, 원소의 원래순서를 유지할 수 있기 때문에 안정적

1. 하나에는 x보다 작은 원소들을 보관하고, 다른 하나에는 x보다 큰 원소들을 보관

2. 입력으로 주어진 연결리스트를 순회하며, brfore리스트 아니면 after리스트에 원소 삽입

3. 순회를 마치면 두 리스트를 합친다

// 연결리스트의 헤드와 분할할 인자값을 넘겨줌
LinkedListNode partition(LinkedListNode node, int x) {
	// 연결리스트를 인스턴스로 만드는게 아니라 변수로 활용 
	// => 처음과 끝 지점을 알아야 next로 연결가능
	LinkedListNode beforeStart=null;
	LinkedListNode beforeEnd=null;
	LinkedListNode afterStart=null;
	LinkedListNode afterEnd=null;
	
	//리스트 분할
	while(node!=null) {
		LinkedListNode next=node.next;
		node.next=null;
		
		if(node.data<x) {
			//before리스트의 끝에 원소를 삽입
			if(beforeStart==null) {
				beforeStart=node;
				beforeEnd=beforeStart;
			} else {
				beforeEnd.next=node;
				beforeEnd=node;
			}
		} else {
			// after리스트의 끝에 원소를 삽입
			if(afterStart==null) {
				afterStart=node;
				afterEnd=afterStart;
			} else {
				afterEnd.next=node;
				afterEnd=node;
			}
		}
		node=next;
	}
	if(beforeStart==null) {
		return afterStart;
	}
	
	// before와 after을 병합한다
	beforeEnd.next=afterStart;
	return beforeStart;
}

위처럼 두개의 연결리스트를 네개의 변수를 사용해 표현하면 리스트의 원소를 '안정적'으로 유지할 수 있다.

하지만 안정적일 필요가 없다면 리스트의 시작과 끝만을 가지고도 원소를 재배치 할 수 있다.

 

해법2) 이미 존재하는 노드를 사용하여 새로운 리스트 만들기

피벗 원소보다 큰 원소는 리스트의 끝에 붙이고 작은 원소는 리스트 앞에 붙인다.

이때 중요한것은 원소를 삽입할 때마다 head와 tail을 갱신해야한다는 것!

LinkedListNode partitionHT(LinkedListNode node, int x) {
	LinkedListNode head=node;
	LinkedListNode tail=node;
	
	while(node!=null){
		LinkedListNode next=node.next;
		if(node.data<x) {
			// head에 노드를 삽입
			node.next=head;
			head=node;
		} else {
			// tail에 삽입
			tail.next=node;
			tail=node;
		}
		node=next;
	}
	// head가 바뀌었기때문에 새로운 head를 반환해야함
	return head;
}

 

 

 

 [ Q5. 리스트의 합 ] 

연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어있는데, 첫번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와같은 방식으로 표현된 숫자 두개가 있을때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라.

예제

입력: (7>1>6)+(5>9>2) 즉, 617+295

출력: 2>1>9 즉, 912

 

- 내 풀이 -

문제점이 있지 연결리스트가 연결이 안되잖아..요..!!

LinkedListNode listSum(LinkedListNode a, LinkedListNode b) {
	int sumInt=makeInt(a)+makeInt(b);
	LinkedListNode sumList=null;
	while(sumInt>0) {
		sumList.data=sumInt%10;
		sumInt/=10;
		sumList=sumList.next;
	}
	return sumList;
}

int makeInt(LinkedListNode node) {
	int sum=0;
	int index=0;
	while(node!=null) {
		sum+=node.data*Math.pow(10, index);
		index++;
		node=node.next;
	}
	return sum;
}

 

- 모범답안 - 

이 문제를 풀 때, 우리가 덧셈을 어떻게 하는지 생각해보면 도움이 된다.

우선 위 문제에서 617+295를 계산하면

1. 일의자리 계산 : 7+5 = 12 이때, 2는 마지막 숫자가되고 1은 다음자리로 넘어간다.

2. 십의자리 계산 : 1+9+1 = 11 이때, 두번째 숫자는 1이 되고 1은 또 다음자리로 넘어간다.

3. 백의자리 계산 : 6+2+1 = 9 이때 마지막 숫자는 9가된다.

위 방법을 재귀적으로 흉내낼 수 있다. 즉, 노드를 하나씩 쌍으로 더하고, 다음자리로 넘겨야 할 수는 다음 노드로 전달

LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2, int carry) {
	if(l1==null && l2==null && carry==0) return null;
	
	LinkedListNode result=new LinkedListNode();
	int value=carry;
	if(l1!=null) {
		value+=l1.data;
	}
	if(l2!=null) {
		value+=l2.data;
	}
	result.data=value%10; // 두번째 숫자
	
	// 재귀
	if(l1!=null||l2!=null) {
		LinkedListNode more=addLists(l1==null? null:l1.next, l2==null?null:l2.next, value>=10? 1:0);
		result.setNext(more);
	}
	return result;
}

 

 [ Q5. 리스트의 합 - 연관문제 ] 

각 자리수가 정상적으로 배열된다고 가정하여 같은 문제를 풀어보자

예제

입력 : (6>1>7) + (2>9>5) 즉, 617+295

출력 : 9>1>2 즉,912

- 모범답안 -

연관문제는 개념적으로 동일(재귀사용 및 자리수 넘긴다는 점)하지만, 구현시 주의사항이 있다.

1. 리스트의 길이가 다른 경우 쉽게 처리 불가 : 따라서 짧은 리스트에 해드에 0을 채워넣는다

2. 원래는 계산 후 꼬리쪽에 붙여나갔지만 여기서는 머리쪽에 붙여나가야한다. 또한 재귀호출 및 넘김수를 같이

전달해야하기때문에 wrapper클래스를 만들어 해결한다

class PartialSum {
	public LinkedListNode sum=null;
	public int carry=0;
}
LinkedListNode addListsReverse(LinkedListNode l1, LinkedListNode l2) {
	int len1=length(l1);
	int len2=length(l2);
	
	// 짧은 리스트에 0을 붙임
	if(len1<len2) {
		l1=padList(l1, len2-len1);
	} else {
		l2=padList(l2,len1-len2);
	}
	
	//두 리스트를 더한다
	PartialSum sum=addListsHelper(l1,l2);
	
	//넘김수(carry)가 존재한다면 리스트 앞쪽에 삽입, 존재하지 않는다면 연결리스트만 반환
	if(sum.carry==0) {
		return sum.sum;
	} else {
		LinkedListNode result=insertBefore(sum.sum, sum.carry);
		return result;
	}
}
int length(LinkedListNode l) {
	if(l==null) {
		return 0;
	} else {
		return 1+length(l.next);
	}
}
PartialSum addListsHelper (LinkedListNode l1, LinkedListNode l2) {
	if(l1==null && l2==null) {
		PartialSum sum=new PartialSum();
		return sum;
	}
	// 작은 자리수를 재귀적으로 더함
	PartialSum sum=addListsHelper(l1.next, l2.next);
	// 현재값에 넘김수를 더함
	int val=sum.carry+l1.data+l2.data;
	// 현재 자릿수를 합한 결과를 삽입
	LinkedListNode full_result=insertBefore(sum.sum, val%10);
	// 지금까지의 합과 넘김수를 반환
	sum.sum=full_result;
	sum.carry=val/10;
	return sum;
}
// 리스트앞에 0 추가
LinkedListNode padList(LinkedListNode l, int padding) {
	LinkedListNode head=l;
	for(int i=0;i<padding;i++) {
		head=insertBefore(head,0);
	}
	return head;
}
// 연결리스트 앞에 노드를 삽입하기 위해 도움주는 함수
LinkedListNode insertBefore(LinkedListNode list, int data) {
	LinkedListNode node=new LinkedListNode();
	if(list != null) {
		node.next=list;
	}
	return node;
}

위처럼 각 메소드를 독립적으로 분리하여 작성하면 코드도 간당해지고 가독성도 높아진다.

 

 

 

 [ Q6. 회문 ] 

주어진 연결리스트가 회문인지 검사하는 함수를 작성하라.

 

 

- 내 풀이 -

처음에는 길이를 알아내서 중간까지만 stack에 넣고 빼면서 비교하려고 했는데

홀수인 경우 가운데 수를 처리하지않는 방법을 고안해내지 못했다.

그래서 리스트를 뒤집어서 저장하고 두 리스트가 같은지 비교하는 방법을 사용했다.

그런데 이것도 리스트를 반대로 저장을 못해서 실패..

=> 1. 홀수인경우 : 길이를 알아내는 것이 아니라 해법2처럼 두개의 포인터 거리를 2배로 순회를 활용

=> 2. 리스트 뒤집기 경우 : 해법1처럼 메소드를 분리하며 새롭게 노드를 새롭게 생성하며 복제

 

 

- 모범답안 -

해법1) 뒤집어서 비교한다

연결리스트를 뒤집어서 원래리스트와 비교

이때 비교는 절반만 하면 OK

boolean bePalindrome(LinkedListNode head) {
	LinkedListNode reverse=reverseAndClone(head);
	return isEqual(head, reverse);
}
LinkedListNode reverseAndClone(LinkedListNode node) {
	LinkedListNode head=null;
	while(node!=null) {
		LinkedListNode n=new LinkedListNode(node.data); //복사
		n.next=head;
		head=n;
		node=node.next;
	}
	return head;
}
boolean isEqual(LinkedListNode node1, LinkedListNode node2) {
	while(node1!=null && node2!=null) {
		if(node1.data!=node1.data) return false;
		node1=node1.next;
		node2=node2.next;
	}
	return node1==null && node2==null;
}

위처럼 늘, 모듈화하는 것을 권장

원소 두개가 들어있는 배열을 반환할 수 있지만 이런 방식은 유지보수가 잘 되지않는다는것.

 

해법2) 순환적 접근법

연결리스트의 앞 절반이 나머지 절반과 같은지를 검사 > 스택을 이용

연결리스트의 길이를 아는 경우 for문을 사용

즉, 차례로 순회하며 반을 스택에 넣고 나머지를 순회하며 비교

이때 두개의 포인터를 사용

★핵심 : 원소개수를 알지 않아도 포인터를 2배씩 움직이면 끝에 도달★

1. 이때 홀수개인경우에는 마지막 포인터가 null이 아닌상황

2. 짝수개인경우에는 마지막 포인터가 null이 상황으로 종료

스택에 원소를 다 넣은 경우 홀수일때 앞선포인터를 하나 넘기고

짝수일때는 그냥 그대로 꺼내면서 비교하면 OK!

boolean palindrome(LinkedListNode head) {
	LinkedListNode fast=head;
	LinkedListNode slow=head;
	
	Stack<Integer> stack=new Stack<Integer>();
	
	// 연결리스트의 앞 절반을 스택에 쌓는다. 
	// => 앞선 포인터(2배빠른) 연결리스트의 끝에 도달하면, 느린포인터는 중간에 도달했다는 사실을 알 수 있다.
	// => 굳이 길이를 먼저 계산할 필요없이 두번씩 앞서나가면 OK!
	while(fast!=null && fast.next!=null) {
		stack.push(slow.data);
		slow=slow.next;
		fast=fast.next.next;
	}
	
	// 원소의 개수가 홀수인 경우 가운데 원소는 skip
	if(fast!=null) {
		slow=slow.next;
	}
	if(slow!=null) {
		int top=stack.pop().intValue();
		// 값이 다르면 회문 불가
		if (top!=slow.data) {
			return false;
		}
		slow=slow.next;
	}
	return true;
}

 

해법3) 재귀적 접근법 : SKIP

 

 

 

 [ Q7. 교집합 ] 

단방향 연결리스트 두개가 주어진 경우, 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫번째 리스트에 있는 k번째 노드와 두번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다.

 

 

- 내 풀이 - 

우선 문제를 이해하지 못했음. 

1. 리스트의 교집합(주소까지 같은)이 있다는 말은 두 리스트의 마지막 노드는 항상 같아야 한다는 것

 => 음.. 아마 중간 부분만 같을 수 도 있잖아 라고 생각을 해서 아닐까? 근데 그렇게 생각하면 마지막 노드는 가르티는 노드가 다르므로 주소값이 다를꺼고 그렇게 전,전,전 노드들을 생각하면 결국 다 다른노드라는 소리! 그래서 마지막 노드가 같아야 한다는 것 아닐까?

2. 주소값을 어떻게 비교하나? node클래스 자체를 비교하는것인가?

class lenAndTail {
	public int len;
	public LinkedListNode tail;
	public lenAndTail(int len, LinkedListNode tail) {
		this.len=len;
		this.tail=tail;
	}
}
LinkedListNode hasIntersection(LinkedListNode l1, LinkedListNode l2) {
	if (aroundNode(l1).tail!=aroundNode(l2).tail) return null;
	
	int len1=aroundNode(l1).len;
	int len2=aroundNode(l2).len;
	if(len1<len2) {
		LinkedListNode temp=l1;
		l1=l2;
		l2=temp;
	}
	int diffLen=len1-len2;
	LinkedListNode intersectionNode=null;
	
	for(int i=0; i<len2; i++) {
		for(int j=0;j<diffLen;j++) {
			l1=l1.next;
		}
		if(l1==l2) {
			intersectionNode=l1;
			intersectionNode=intersectionNode.next;
		}
		l1=l1.next;
		l2=l2.next;
	}
	return intersectionNode;
}

// 길이와 마지막 노드를 반환하는 메소드
lenAndTail aroundNode(LinkedListNode node) {
	lenAndTail lt=new lenAndTail(0, node);
	while(node!=null) {
		lt.len++;
		lt.tail=node;
		node=node.next;
	}
	return lt;
}

 

 

- 모범답안 -

리스트의 교집합 판별 방법은 두가지

① 해시테이블을 사용 이때 중요한것은 값이 아닌 메모리 주소를 저장해야한다는 것!

하지만 이방법은 별도의 공간을 필요로 하기 때문에 아래 방법 사용

② 연결리스트의 교집합이 존재한다는 말은 두 리스트의 마지막은 항상 같아야 한다는 것

따라서 끝까지 순회한 뒤 마지막 노드가 같은지 비교하면 OK!

 

*겹치는 노드를 찾기위해 마지막에서부터 반대로 순회하면서 '분기'하는 지점 찾기 > 하지만 단반향연결리스트에서

반대로 순회하는 것 불가능. 만약 연결리스트 길이가 같다면 순차적으로 순회하며 겹치는 부분을 찾으면 됨

 

* 위를 기반으로 구현절차는 다음과 같다.

1. 각 연결리스트를 순회하며 길이와 마지막 노드를 구함

2. 마지막 노드가 다르다면 교집합 없음

3. 각 리스트의 시작에 포인터를 놓음

4. 두 리스트의 길이 차 만큼 긴 리스트를 포인터를 움직여 위치시킨다.

5. 두 포인터가 같아질때까지 두 리스트를 함께 순회.

public static LinkedListNode findIntersection(LinkedListNode list1, LinkedListNode list2) {
	if(list1==null||list2==null) return null;
	
	//1. 마지막 노드와 길이를 구함
	Result result1= getTailAndSize(list1);
	Result result2= getTailAndSize(list2);
	
	
	//2. 마지막 노드가 다르면 교집합이 없다는 것
	if(result1.tail!=result2.tail) return null;
	
	//3. 각 연결리스트 시작에 포인터 세팅
	LinkedListNode shorter=result1.size<result2.size? list1:list2;
	LinkedListNode longer=result1.size>result2.size? list1:list2;
	System.out.println(list1);
	System.out.println(list2);
	
	//4. 길이가 긴 연결리스트의 포인터를 차이만큼 앞으로 움직임
	longer=getKthNode(longer,Math.abs(result1.size-result2.size));
	
	//5. 두 포인터가 만날때까지 함께 앞으로 움직임
	while(shorter!=longer) {
		shorter=shorter.next;
		longer=longer.next;
	}
	//6. 둘 중 하나 반환
	return longer;
}

public static class Result {
	public LinkedListNode tail;
	public int size;
	public Result(LinkedListNode tail, int size) {
		this.tail=tail;
		this.size=size;
	}
}

public static Result getTailAndSize(LinkedListNode list) {
	if(list==null) return null;
	int size=1;
	LinkedListNode current=list;
	while(current.next!=null) {
		size++;
		current=current.next;
	}
	return new Result(current, size);
}

public static LinkedListNode getKthNode(LinkedListNode head,int k) {
	LinkedListNode current=head;
	while(k>0 && current!=null) {
		current=current.next;
		k--;
	}
	return current;
}

 

 

 

 

 [ Q8. 루프발견 ] 

순환 연결리스트(circular linked list)가 주어졌을때, 순환되는 부분의 첫번째 노드를 반환하는 알고리즘을 작성하라. 순환 연결 리스트랑 노드의 next포인터가 앞선 노드들 가운데 어느 하나를 가르키도록 설정되어있는, 엄밀히 말해서 변질된 방식의 연결리스트를 의미한다.

예제

입력 : a>b>c>d>e>c (앞에나온 c와 동일)

출력 : c

 

- 내 풀이 -

1. HashMap<node,boolean>사용

2. 순회하며 넣고 공통키를 발견한 경우 키 노드 반환

... 루프찾기 공부하고 다시 풀어볼것임.

	LinkedListNode findLoopPoint(LinkedListNode node) {
		HashMap<LinkedListNode, Boolean> map=new HashMap<LinkedListNode, Boolean>();
		LinkedListNode loopPoint=node;
		while (loopPoint!=null) {
			if(map.containsKey(loopPoint)) return loopPoint;
			map.put(loopPoint,true);
		}
		return null;
	}

 

 

- 모범답안 -

이 문제는 연결리스트에 루프가 존재하는지 찾는 고전적인 문제를 변형한 것

=> '패턴매칭(Pattern Matching)'을 활용

1. 연결리스트에 루프가 있는지 검사

대표적인 검사방법은 FastRunner/SlowRunner접근법

FastRunner는 한번에 두걸음씩 내딛고, SlowRunner는 한걸은씩 내딛는다. 서로 다른 속도로 돌기 때문에 결국 만나게 된다는 것이 핵심 

루프문제 풀어보고 다시 풀어보기. - 318p