나는 한동안 클래스를 위해 Java 프로젝트에서 일하고 있습니다. 이것은 연결 목록 (여기서는라고하며라는 AddressList단순 노드를 포함 함 ListNode) 의 구현입니다 . 문제는 모든 것이 재귀 알고리즘으로 이루어져야한다는 것입니다. 나는 한 가지 방법으로 모든 것을 잘 할 수 있었다.public AddressList reverse()
ListNode :
public class ListNode{
public String data;
public ListNode next;
}지금 내 reverse함수는 재귀를 허용하기 위해 인수를 취하는 도우미 함수를 호출합니다.
public AddressList reverse(){
return new AddressList(this.reverse(this.head));
}내 도우미 기능에 private ListNode reverse(ListNode current).
현재 스택을 사용하여 반복적으로 작동하지만 사양이 요구하는 것은 아닙니다. 나는 C에서 재귀 적으로 뒤집어서 자바 코드로 직접 변환 한 알고리즘을 찾았지만 작동했지만 이해하지 못했다.
편집 : 신경 쓰지 마세요, 그동안 알아 냈어요.
private AddressList reverse(ListNode current, AddressList reversedList){
if(current == null)
return reversedList;
reversedList.addToFront(current.getData());
return this.reverse(current.getNext(), reversedList);
}내가 여기있는 동안이 경로에 문제가있는 사람이 있습니까?
답변
하나의 답장에 그것을 설명하는 코드가 있지만, 작은 질문을하고 답함으로써 밑바닥부터 시작하는 것이 더 쉬울 수 있습니다 (이것은 The Little Lisper의 접근 방식입니다).
- null (빈 목록)의 반대는 무엇입니까? 없는.
- 단일 요소 목록의 반대는 무엇입니까? 요소.
- n 요소 목록의 반대는 무엇입니까? 나머지 목록의 역순에 첫 번째 요소가옵니다.
public ListNode Reverse(ListNode list)
{
if (list == null) return null; // first question
if (list.next == null) return list; // second question
// third question - in Lisp this is easy, but we don't have cons
// so we grab the second element (which will be the last after we reverse it)
ListNode secondElem = list.next;
// bug fix - need to unlink list from the rest or you will get a cycle
list.next = null;
// then we reverse everything from the second element on
ListNode reverseRest = Reverse(secondElem);
// then we join the two lists
secondElem.next = list;
return reverseRest;
}답변
인터뷰에서이 질문을 받았는데, 조금 긴장해서 더듬 거려서 짜증이났다.
이것은 reverse (head, NULL)로 호출되는 단일 연결 목록을 뒤집어 야합니다. 그래서 이것이 당신의 목록이라면 :
1-> 2-> 3-> 4-> 5-> null 다음과 같이됩니다. 5-> 4-> 3-> 2-> 1-> null
//Takes as parameters a node in a linked list, and p, the previous node in that list
//returns the head of the new list
Node reverse(Node n,Node p){
if(n==null) return null;
if(n.next==null){ //if this is the end of the list, then this is the new head
n.next=p;
return n;
}
Node r=reverse(n.next,n); //call reverse for the next node,
//using yourself as the previous node
n.next=p; //Set your next node to be the previous node
return r; //Return the head of the new list
}
편집 : 이것에 대해 6 개의 편집처럼 끝났고, 그것이 여전히 나를 위해 조금 까다 롭다는 것을 보여줍니다.
답변
나는 절반을 통과했지만 (널이 될 때까지, 주각이 제안한 하나의 노드) 재귀 호출을 한 후 트랙을 잃었습니다. 그러나 주각으로 게시물을 읽은 후 다음과 같이 생각했습니다.
Node reverse(Node head) {
// if head is null or only one node, it's reverse of itself.
if ( (head==null) || (head.next == null) ) return head;
// reverse the sub-list leaving the head node.
Node reverse = reverse(head.next);
// head.next still points to the last element of reversed sub-list.
// so move the head to end.
head.next.next = head;
// point last node to nil, (get rid of cycles)
head.next = null;
return reverse;
}답변
여기에 또 다른 재귀 솔루션이 있습니다. 다른 것보다 재귀 함수 내에 코드가 적으므로 조금 더 빠를 수 있습니다. 이것은 C #이지만 Java는 매우 유사 할 것이라고 생각합니다.
class Node<T>
{
Node<T> next;
public T data;
}
class LinkedList<T>
{
Node<T> head = null;
public void Reverse()
{
if (head != null)
head = RecursiveReverse(null, head);
}
private Node<T> RecursiveReverse(Node<T> prev, Node<T> curr)
{
Node<T> next = curr.next;
curr.next = prev;
return (next == null) ? curr : RecursiveReverse(curr, next);
}
}답변
알고리즘은 다음 모델에서 작업해야합니다.
- 머리를 추적하다
- 링크 목록 끝까지 반복
- 역 연결
구조:
Head
|
1-->2-->3-->4-->N-->null
null-->1-->2-->3-->4-->N<--null
null-->1-->2-->3-->4<--N<--null
null-->1-->2-->3<--4<--N<--null
null-->1-->2<--3<--4<--N<--null
null-->1<--2<--3<--4<--N<--null
null<--1<--2<--3<--4<--N
|
Head암호:
public ListNode reverse(ListNode toBeNextNode, ListNode currentNode)
{
ListNode currentHead = currentNode; // keep track of the head
if ((currentNode==null ||currentNode.next==null )&& toBeNextNode ==null)return currentHead; // ignore for size 0 & 1
if (currentNode.next!=null)currentHead = reverse(currentNode, currentNode.next); // travarse till end recursively
currentNode.next = toBeNextNode; // reverse link
return currentHead;
}산출:
head-->12345
head-->54321답변
LISP와 비슷한 더 깨끗한 솔루션이라고 생각합니다.
// Example:
// reverse0(1->2->3, null) =>
// reverse0(2->3, 1) =>
// reverse0(3, 2->1) => reverse0(null, 3->2->1)
// once the first argument is null, return the second arg
// which is nothing but the reveresed list.
Link reverse0(Link f, Link n) {
if (f != null) {
Link t = new Link(f.data1, f.data2);
t.nextLink = n;
f = f.nextLink; // assuming first had n elements before,
// now it has (n-1) elements
reverse0(f, t);
}
return n;
}답변
나는 이것이 오래된 게시물이라는 것을 알고 있지만 대부분의 답변은 꼬리 재귀가 아닙니다. 즉 재귀 호출에서 돌아온 후 일부 작업을 수행하므로 가장 효율적이지 않습니다.
다음은 꼬리 재귀 버전입니다.
public Node reverse(Node previous, Node current) {
if(previous == null)
return null;
if(previous.equals(head))
previous.setNext(null);
if(current == null) { // end of list
head = previous;
return head;
} else {
Node temp = current.getNext();
current.setNext(previous);
reverse(current, temp);
}
return null; //should never reach here.
} 전화 :
Node newHead = reverse(head, head.getNext());