[Java 기본 알고리즘] (5) 연결리스트

package LinkedListBasic;

class ListNode{
	int val;
	ListNode next;
	
	ListNode(int x){
		this.val = x;
	}
}
public class LinkedList1 {
	public static void main(String[] args) {
		ListNode l1=new ListNode(2);
		l1.next = new ListNode(4);
		l1.next.next=new ListNode(3);
		//[2,4,3]
		ListNode l2=new ListNode(5);
		l2.next=new ListNode(6);
		l2.next.next=new ListNode(2);
		//[5,6,2]
		ListNode node = solve(l1,l2);
		while(node!=null) {
			System.out.println(node.val);
			node =node.next; //node에 next를 지정해야 반복 가능
		}
		}
	//AddTwoNumbers
	//포인터를 어떤식으로 넘기는지
	//입력값을 리스트노드 타입으로 주고, 각각의 합을 출력 [Next->Next->null :null은 탈출]
	//결과값 리스트는 : 더미 데이터로 0,Next를 만들고, 각각의 합을 출력하는데 일의 자리수를 넘어가면 다음 노드에 +1
							
	//문제 해결 -> ListNode는 행으로, 칼럼으로 하나의 리스트노드를 형성한다.
	//
	public static ListNode solve(ListNode l1, ListNode l2) {
		//1. ds
		
		// 값이 0인 더미 데이터 생성
		ListNode newHead = new ListNode(0);
		
		//l1, l2 카피하고, newHead 생성 -> 일반적으로 카피해서 사용
		ListNode p1=l1, p2=l2, p3=newHead;	
		
		//합이 일의 자리가 넘어갈 때, 필요한 변수 생성
		int carry=0;
		
		//2. for, while
		while(p1!=null||p2!=null) {	//p1과 p2가 널이 탈출조건
			if(p1 !=null) {
				carry += p1.val;	//p1 : 2,4,3 -> carry에 2 담는다.
				p1=p1.next;		//p1.next가 4로 넘어가므로 -> 2, next를 날리고 4, next가 p1			
			}
			if(p2 !=null) {
				carry += p2.val;	//p2 : 5,6,2 -> carry에 5 담는다.
				p2=p2.next;		//p2.next가 6으로 넘어가므로 -> 5, next를 날리고 5, next가 p2
			}
			//carry에 p1과 p2의 합이 담겨져 있다. -> p3를 만들어 담기
			p3.next = new ListNode(carry%10);	//일의자리로만 저장이 가능하므로 몫을 저장하고, 나머지를 뒤로 보낸다.
			p3 =p3.next;	//7,next에서 0,next으로 넘어가기 위해
			//4+6이 10인데, 1을 올려주기위해
			carry /=10;		//carry에 몫을 넘긴다.
			
			
		}
		//마지막 자리에서도 일의 자리를 초과할 수 있기 떄문에 -> 생성
		if(carry==1) p3.next=new ListNode(1);
		
		return newHead.next;	//넘길 때 더미데이터를 제외한 나머지데이터만
		
	}
		
}

 

 

package LinkedListBasic;

import java.util.PriorityQueue;
import java.util.Queue;

public class LinkedList2 {
	
	public static void main(String[] args) {
		LinkedList2 a = new LinkedList2();

		ListNode l1 = new ListNode(1);
		l1.next = new ListNode(4);
		l1.next.next = new ListNode(5);

		ListNode l2 = new ListNode(1);
		l2.next = new ListNode(3);
		l2.next.next = new ListNode(4);

		ListNode l3 = new ListNode(2);
		l3.next = new ListNode(7);

		ListNode[] list = new ListNode[3];
		list[0] = l1;
		list[1] = l2;
		list[2] = l3;
		ListNode result = a.solve(list);
		a.print(result);
	}
	//K개의 정렬된 리스트 병합
	//K개의 오름차순으로 정렬된 연결리스트를 하나의 정렬된 연결리스트로 병합하고 리턴
	//중복 허용
	
	//문제 해결
	//mergesort 이용, minheap 이용
	
	//minHeap구조로 pq를 만들기
	//L1 (1,4,5)
	//L2(1,3,4) L3(2,6)
	
	//ListNode list1 = 1->4->5,
	//ListNode list2 = 1->3->4, ListNode list3 = 2->6
	
	//pq에 ListNode타입으로 minHeap 생성해 -> L1에 가장 작은 값만 만들기 -> 가장 작은 값만 남기게 하려면 ->
	//L1에서 queue.poll()을 하고 제일 작은 값을 빼서 담는다 -> list1의 제일 1은 결과를 담을 ListNode res에 넣는다. (res=1);
	//-> L1의 1이 빠졌기 떄문에 minHeap 특성으로, L2가 최상단이 되고, L2의 1이 빠지면, L3이 올라가서, L3의 2를 pq에 넣는다. [minHeap의 구조]
	//-> L1의 1이 빠지면 4,5가 앞으로 땡겨진다. [연결리스트의 구조]
	//-> listp = 1-> 1-> 2
	//res의 카피본을 이용해 더미데이터 0을 추가한 후, 그 이후 데이터를 원본으로 넘긴다.
	
	//구현 부분
	public ListNode solve(ListNode[] lists) {
		//1. ds
		//queue를 이용한 minheap 만들기
		//1. 상위 버전
		Queue<ListNode> q= new PriorityQueue<>((a,b)-> a.val-b.val);
		//2. 하위 버전
//		Queue<ListNode> q = new PriorityQueue<>(new Comparator<>(){	//비교자 메서드를 이용한 조건
//			public int compare(ListNode l1, ListNode l2) {
//			return l1.val-l2.val;
//		}
//	});
//		//3. Comp를 이용
//		Queue<ListNode> q = new PriorityQueue<>(Comp);
//	
		ListNode head = new ListNode(0);	//더미 데이터 생성
		ListNode res=head;					//결괏값에 더미 데이터 추가
	
		//2. for, while
		//Lists를 ListNode 타입으로
		for(ListNode list: lists) {	//ListNode인 lists를 list로 반복
			if(list != null)		//리스트가 null이 아닐때마다,
				q.offer(list);		//pq에 ListNode를 삽입
		}
		
		//pq가 빌때까지 하나씩 빼는 작업
		while(!q.isEmpty()) {				//pq가 빌떄가 탈출조건
			ListNode node = q.poll();		//node에서 pq의 최상단을 빼서 넣는다.
			System.out.println("poll : "+node.val);	//1,1,2 -> L1, L2, L3
			res.next = node;				//최초에 결괏값의 더미 데이터에 node를 넣어주도록 세팅
			res=res.next;					//결괏값 리스트노드가 다음 데이터를 가리키도록
			
			//가장 작은 값들을 뺀 이후에 각각의 리스트노드에 다음 값을 땡겨오는 작업 [1,4,5] -> [4,5] -> 포인터가 1에서 4를 가리키도록
			if(node.next !=null)			//L1에 1이 날라왔기 때문에, node.next가 null이 아니다. 
				q.offer(node.next);			//날라온 1를 넣기위해서, pq에 node.next를 넣는다.
											//즉, 1이 결괏값에 들어가고, 그 다음 데이터를 땡긴다.
		}
		
		return head.next;					//더미 데이터 다음부터 넘기기 위해서
		
	}

//	//3. Comp를 이용
//	Comparator <ListNode> Comp = new Comparator<>() {
//		public int compare (ListNode l1, ListNode l2) {
//			return l1.val- l2.val;
//		}
//	};
//	
	private void print(ListNode node) {
		while(node != null) {
			System.out.println(node.val);		//[res next의 예시] 1을 찍는다. 4를 찍는다.
			 node = node.next;					//다음 4를 찍어야 하기 떄문에, node의 next를 4의 node로 가리키기 위해 next
			 									//다음 5를 찍어야 하기 때문에,	node의 next를 5의 node로 가리키기 위해 next 
		}
			
	}
	

}

 

 

package LinkedListBasic;

public class LinkedList3 {
	public static void main(String[] args) {
		ListNode l1 = new ListNode(1);
		l1.next = new ListNode(2);
		l1.next.next = new ListNode(3);
		
		System.out.print("입력값 ");
		printNode(l1);
		ListNode head = reverseList(l1);
		
		System.out.print("출력값 ");
		printNode(head);
	}
	//Reverse LinkedLists
		//주어진 단일 연결 리스트를 이용해 reverse해서 reversed lists를 리턴
		//-> singly linked list
		//비어있을 경우 비어있는 값을 리턴

		//1. singly linked list -> int val1과 ListNode인 Next가, Next는 다음 ListNode를 가리키기 떄문에 ListNode로 만든다.
		//2. doubly linked list -> val1 앞에 Head가 붙고, 뒤에 Next가 붙은 구조로 서로 연결되어 있는 구조
		
		//문제 해결 -> 입력값을 보고 결괏값을 생각하고, 구현	
		//1. val(1)의 next를 null로 만든다.		
		//2. val(1)을 앞에 next가 가리킨다.		-> cur.next에 val1을 넣는다.
		//3. next가 뒤에 값들을 가리켜야한다.		-> cur.next =prev, prev=cur
		//즉, next가 그 다음 prev가 되고, prev는 cur이 된다.
		//4. cur 포인터를 한 칸 뒤로 보낸다.		-> cur = next
		
	//구현 부분
	public static ListNode reverseList(ListNode cur) {
		//1. ds
		//담을 그릇 생성
		ListNode next =null;
		ListNode prev =null;
		
		
		//2. for while
		while(cur!=null) {		//현재값이 null일 때 탈출조건
			//처음에 cur의 next를 분리
			next = cur.next;		//cur의 다음 step을 위해, 다음 순서들을 다른 방에 넣기 위해 분리
			//cur의 next에 prev를 넣기 -> cur의 next에 0이 들어간다. cur: 1,0
			cur.next=prev;
			//현재 cur를 prev에 넣는다. -> 1,0이 prev이기 때문에 2,next가 가리키게 하기 위해서-> 2,next와 1,0을 3,next에서 가리키기위해 ->prev에 넣는다.
			prev =cur;
			//2,next -> 3,0을 위해서 [2,n -> 3,0가 next이므로, cur로 만든다.]
			cur = next;				//이후 next = cur.next로 이동
		}
		return prev;
	}

	public static void printNode(ListNode head) {
		System.out.println("printNode: ");
		while(head != null) {
			System.out.println(head.val);
			head = head.next;
		}
		System.out.println();
	}
	
	
}