Обратный поиск связанного списка

Question

Моя проблема: задана функция для изменения связанного списка.

Моя попытка на него в C был:

ListNode *reverse(ListNode *head) 
{ 
    if(head == NULL || head->next == NULL) 
     return head; 

    ListNode *temp = head->next; 
    ListNode *retP = reverse(temp); 
    temp->next = head; 
    head->next = NULL; 
    return retP; 
} 

Но я не думаю, что это правильно. Я хочу быть в состоянии сделать это на Java, и я в тупике. Любая помощь будет оценена по достоинству. Пожалуйста, помогите мне начать

Answer 1

Итеративно

public reverseListIteratively (Node head) { 
if (head == NULL || head.next == NULL) 
return; //empty or just one node in list 

Node Second = head.next; 

//store third node before we change 
Node Third = Second.next; 

//Second's next pointer 
Second.next = head; //second now points to head 
head.next = NULL; //change head pointer to NULL 

//only two nodes, which we already reversed 
if (Third == NULL) 
return; 

Node CurrentNode = Third; 

Node PreviousNode = Second; 

while (CurrentNode != NULL) 
{ 
Node NextNode = CurrentNode.next; 

CurrentNode.next = PreviousNode; 

/* repeat the process, but have to reset 
    the PreviousNode and CurrentNode 
*/ 

PreviousNode = CurrentNode; 
CurrentNode = NextNode; 
} 

head = PreviousNode; //reset the head node 
} 

Рекурсивный

public void recursiveReverse(Node currentNode) 
{ 
//check for empty list 
if(currentNode == NULL) 
    return; 

/* if we are at the TAIL node: 
    recursive base case: 
*/ 
if(currentNode.next == NULL) 
{ 
//set HEAD to current TAIL since we are reversing list 
head = currentNode; 
return; //since this is the base case 
} 

recursiveReverse(currentNode.next); 
currentNode.next.next = currentNode; 
currentNode.next = null; //set "old" next pointer to NULL 
} 

Источник, с объяснением (после того, как с помощью Google в течение 3 секунд) http://www.programmerinterview.com/index.php/data-structures/reverse-a-linked-list/

Answer 2

Если вы хотите, чтобы отменить список в Java,

Collections.reverse(List list) 

Если вы хотите узнать, как это реализовано или хотите сделать это вручную, посмотрите на the JDK sources of java.util.Collections.

Answer 3

public Node reverse(Node node){ 
    Node p=null, c=node, n=node; 
    while(c!=null){ 
     n=c.next; 
     c.next=p; 
     p=c; 
     c=n; 
    } 
return p; 
}