바위타는 두루미

문제 단방향 연결리스트 두개가 주어졌을때 이 두리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다. 해법 교집합의 유무를 판별하기 위해서는 우선 각 리스트의 마지막노드가 같아야하고, 같은 길이의 출발점에서부터 순차적으로 탐색을 했을때 동시에 방문하는 노드가 같은 점이 잇어야한다. 1. 각 연결리스트를 순회하면서 길이와 마지막 노드를 구한다. 2. 길이가 긴쪽의 리스트에서 짧은쪽과의 차이만큼 시작포인터를 옮긴다. 3. 두 포인터가 같아질때까지 두 리스트를 함께 순회한다. def lengt..

문제 주어진 연결리스트가 회문(Palindrome)인지 검사하는 함수를 작성해라. 해법 1. 뒤집어서 비교하기 연결리스트를 뒤집어서 비교해서 같으면 그 연결리스트는 회문이며, 비교는 반절만 하면된다. def get_reverse(node): reverse_head = None while node is not None: n = Node(node.data) n.next = reverse_head reverse_head = n node = node.next return reverse_head def isEqual(n1, n2): while n1 is not None and n2 is not None : if n1.data != n2.data : return false n1 , n2 = n1.next , n2...

문제 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 즉 첫번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와같은 방식으로 표현된 숫자 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라. 예제 입력 (7->1->6) +(5-> 9-> 2) 출력 ( 2->1-> 9) => 617 + 295 = 912 연관문제 각 자릿수가 정상적으로 배열된다고 가정하고 같은 문제를 풀어보자 예제 입력 (6->1->7) +( 2->9->5) 출력 ( 9->1->2) => 617 + 295 = 912 해결법 기본 문제는 우리가 덧셈을 하듯이 더한 숫자의 1의 자리 숫자로 노드를 만들고 캐리를 넘김..