單鏈表就地逆置算法 單鏈表的就地逆置的算法?
單鏈表的就地逆置的算法?單鏈表就地逆置有幾種方法?兩種單鏈表的局部反轉(遞歸和普通循環)1。采用遞歸算法,對無前導節點的單鏈表(A1、A2、A3、A4、A5、A6)進行反向設置后得到(A6、A5、A4
單鏈表的就地逆置的算法?
單鏈表就地逆置有幾種方法?
兩種單鏈表的局部反轉(遞歸和普通循環)1。采用遞歸算法,對無前導節點的單鏈表(A1、A2、A3、A4、A5、A6)進行反向設置后得到(A6、A5、A4、A3、A2、A1)。考慮遞歸算法,如果只有一個節點,它將直接返回。如果有兩個節點(A1,A2),則要執行的操作是:A2->next=A1,A1->next=NullReturn A2a2是新的頭節點。如果有三個節點,則應首先反轉子鏈(A2,A3),并返回子鏈的新頭節點。然后將子鏈(A2,A3)看作一個復合節點A2”,形成一個新的二進制(A1,A2”),然后可以執行具有相同前面的操作:A2“->next=A1,A1->next=NullReturn A3”,即可以以相同的方式獲得多個節點,node*reverse(node*head){node*P=head if(P==null)return null//如果是空鏈表,則返回一個空節點*q=P->next if(q==null)return P//如果只有一個節點,則返回else head=reverse(q)//記錄子序列的新head q->next=P//將當前節點和反向子序列視為前后兩個節點P、q。執行相應的反向操作p->next=null return head//返回新子序列的head節點}2。使用常用算法反向(head inserting method重建前導節點的新鏈表)node*reverse(node*head){node*P=head->next If(P)//如果鏈表不為空,則反向。否則,空操作{node*q=P->next head->next=null//頭節點是分開的,而(P){P->next=head->next//在建立鏈表head->next=P if(q)//在操作空指針時,必須非常小心并且容易出錯{P=q}q=P->next}否則break}return頭}
例如,鏈表a-> B-> C-> D有頭和尾。局部反轉是指:a next=&BB->next=&CC->next=&DD->next=0反轉后:B->next=&AC->next=&BD->next=&CA->next=0。所謂局部反轉,是指在運算中遇到a->next=&B時,重寫為B->next=&a
]例如鏈表a->B->C->D的頭是a,尾是d,局部反轉是指a<-B<-c<-Da成為表尾,d成為表頭。假設structlink{intvaluestructlink*next}structlinka,B,C,Da->next=&BB->next=&CC->next=&DD->next=0,在反轉之后,B->next=&AC->next=&BD->next=&CA->next=0,所謂的局部反轉意味著在操作中遇到a->next=&B時,它被重寫為B->next=&A