Question

单链表就地逆置有几种方法

Answer 1

单链表就地逆置的两种(递归与普通循环)
1.用递归算法,对于不带头结点的单链表（a1,a2,a3,a4,a5,a6）逆置后的结果为（a6,a5,a4,a3,a2,a1）
考虑递归算法，若只有一个结点，则直接返回，若存在两个结点（a1,a2）则需要做的操作有：　　　　　　a2->next=a1;a1->next=NULL;return a2;
a2即新的头结点，若有三个结点,则应先将子链（a2,a3）先逆置且返回该子链的新的头结点，然后把子链（a2,a3）当作一个复合结点a2',
组成新的二元组（a1,a2'）然后就可以执行前面相同的操作：a2'->next=a1;a1->next=NULL;return a3';即可，多个以上的结点可同理得到，
Node *Reverse(Node *head)
{
Node *p=head;
if(p==NULL)
return NULL;　　　　　//若是空链表，返回空
Node *q=p->next;
if(q==NULL)
return p;　　　　　//若只有一个结点，直接返回
else
head=Reverse(q);　　//记录子序列的新的头结点
q->next=p;　　　　　//当前结点与已经逆置的子序列看成是前后的两个结点p,q，作相应的逆置操作
p->next=NULL;
return head; 　　//返回新的子序列的头结点
}
2.用普通算法循环逆置（头插法重新建立带头结点的新链表）
Node *Reverse(Node *head)
{
Node *p=head->next;
if(p)//若链表不为空，则逆置，否则，空操作
{
　Node *q=p->next;
　　head->next=NULL;//头结点分离
　　while(p)
　　{
　　p->next=head->next;　//头插法建立链表
　　head->next=p;
　　if(q) //操作空指针的时候一定要非常注意，很容易出错
　　{
　　　p=q;
　　　q=p->next;
　　}
　　else
　　　break;
　　}
}
return head;
}

Answer 2

typedef struct ListNode{
ListNode *next;
Element data;
}ListNode, *pList;
这是我做的单链表逆序三个不同的算法，2个递归的以及一个非递归的

pList ReverseList( pList head ){
if( !head || !(head->next) )
return head;
pList ph = ReverseList( head->next );
head->next->next = head;
head->next = NULL;
return ph;
}
pList ReverseList( pList head , pList &tail ){
if( !head || !(head->next) ){
tail = head;
return head;
}
pList pt;
pList ph = ReverseList( head->next , pt );
pt->next = head;
head->next = NULL;
tail = head;
return ph;
}
pList ReverseListNonRec( pList head ){
if( !head || !(head->next) )
return head;
pList h = NULL,h1 = head;
while( head ){
h1 = head->next;
head->next = h;
h = head;
head = h1;
}
return h;
}

Answer 3

能够实现的方法都是好方法。

Answer 4

1

Answer 5

so？