首页 > 试题广场 >

求链表的逆序 。 链表的结点:

[问答题]

链表的结点 :

typedef struct Node{
   int data;
   struct Node* next;

} Node;


已知链表的头结点head, 写一个函数把这个链表逆序:

Node* reverse(Node *head);

//递归方式 
Node* reverse(Node *head)
{  
    //如果链表为空或者链表中只有一个元素  
    if(head==NULL || head->next==NULL)  
        return head;  
    else  
    { 
	   Node* newhead=reverse(head->next);//先反转后面的链表  
	   head->next->next=head;//再将当前节点设置为其然来后面节点的后续节点
       head->next=NULL;  
       return newhead;  
    }  
} 
发表于 2015-10-28 08:56:37 回复(0)
XQ头像 XQ
public void ReverseLink(Node head){
		Node a;
		Node b;
		a= head.getNext();
		if(a==null){
			System.out.println("链表为空");
			return;
		}
		while(a.getNext()!=null){//链表翻转
			b = a.getNext();
			a.setNext(b.getNext());
			b.setNext(head.getNext());
			head.setNext(b);
		}
		head = head.getNext();
		while(head.getNext()!=null){//循环输出
			System.out.print(head.getValue()+" ");
			head = head.getNext();
			
		}
		System.out.println(head.getValue());
		
	}
	

发表于 2015-10-28 14:52:36 回复(0)
node *reverse(node *head)
{
   node *p1,*p2,*p3;
   p1=head;//p1指向头结点
   p2=p1->next; 
   while(p2)
{
    p3=p2->next;
    p2->next=p1;//节点逆置
    p1=p2; //逆置后p1后移一位
    p2=p3; //逆置后p2后移一位  }
 head->next=NULL;//原头结点,现为末节点,next置为空
 head=p1; //此时p1已指向原末节点,此时置为头结点
 return head;
}

面试宝典上的,一直用的这个

编辑于 2015-10-28 13:30:31 回复(0)
classSolution {
public:
ListNode* ReverseList(ListNode* pHead) {
        if( pHead == NULL)//如果聊表为空,直接返回NULL
{
returnNULL;
}
ListNode *pPrev = NULL;//标记当前反转结点的前一个节点
ListNode *temp = pHead;//标记当前结点
ListNode *pNext = NULL;//标记当前结点的下一个节点
ListNode *ReverseHead = NULL;//标记反转后链表的头结点地址
while(temp)//遍历链表
{
if(temp->next == NULL)//如果当前链表的的下一个节点为空,则当前结点为反转后链表的头结点
{
ReverseHead = temp;
}
pNext = temp->next;//先记录当前结点 的  下一个节点地址
temp->next = pPrev;//更改指针方向
pPrev = temp;//更改  pPrev  地址
temp = pNext;//指针移动向下  遍历链表
}
returnReverseHead;//返回  反转 链表的 头结点地址  OK了  ^_^
}
};
发表于 2015-10-28 13:09:54 回复(0)
链表这种题,很简单,需要的是细心。思路,用三个值记录连续的三个点,一个是需要反转的指向节点,一个记录中间节点,一个记录下一个节点。然后一次向下移动即可。具体代码查看剑指offer里面题目讨论,以有很多人提交代码。
发表于 2015-10-28 09:32:18 回复(0)
//笔试遇到几次了,这是我自己的解答,不知道对不对
Node* reverse(Node *head){
 if(head==NULL)
 return head;
 Node *curr1=head,*curr2=head->next;
 head->next=0;
 while(curr2!=NULL){
 Node *temp = curr2->next;
 curr2->next = curr1;
 curr1 = curr2;
 curr2 = temp;
 }
 return curr1;
}
发表于 2015-10-28 00:24:55 回复(0)