反转链表

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

如果要

在 Java 中反转列表，请使用

Collections.reverse(List list)

如果您想知道如何实现或想手动完成，请查看 JDK java.util.Collections源 .

Answer 2

迭代

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
}

来源，有解释（使用谷歌 3 秒后）http://www.programmerinterview.com/index.php/data-structures/reverse-a-linked-list/

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;
}