鏈表逆轉(zhuǎn)輸出
方案一：head 作為已知首節(jié)點(diǎn)茄蚯，最后節(jié)點(diǎn)指向null， 使用三個(gè)指針便利鏈表发乔，逐個(gè)節(jié)點(diǎn)進(jìn)行反轉(zhuǎn)
實(shí)現(xiàn)代碼：
struct ActList {
? ? ActList * next;
};
ActList * reverseList(ActList * head) {
? ?
? ? if (head == NULL || head -> next == NULL) {
? ? ? ? // 少于兩個(gè)節(jié)點(diǎn)無需反轉(zhuǎn)
? ? ? ? return head;
? ? }
? ?
? ? ActList * p;
? ? ActList * q;
? ? ActList * r;
? ?
? ? p = head;
? ? q = head -> next;
? ? head -> next = NULL;
? ?
? ? while (q) {
? ? ? ? r = q -> next;
? ? ? ? q -> next = p;
? ? ? ?
? ? ? ? p = q;
? ? ? ? q = r;
? ? }
? ?
? ? head = p;
? ?
? ? return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
方案二： 對(duì)于一條鏈表搓谆，從第2個(gè)節(jié)點(diǎn)到第N個(gè)節(jié)點(diǎn)薯嗤，依次逐節(jié)點(diǎn)插入到第1個(gè)節(jié)點(diǎn)(head節(jié)點(diǎn))之后，(N-1)次這樣的操作結(jié)束之后將第1個(gè)節(jié)點(diǎn)挪到新表的表尾
代碼：
ActList* ReverseList2(ActList* head)
{
ActList* p;
ActList* q;
p=head->next;
while(p->next!=NULL){
q=p->next;
p->next=q->next;
q->next=head->next;
head->next=q;
}
p->next=head;//相當(dāng)于成環(huán)
head=p->next->next;//新head變?yōu)樵環(huán)ead的next
p->next->next=NULL;//斷掉環(huán)
return head;?
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
方案三：循環(huán)
ActList * reverseList3 (ActList * head) {
? ? if (head == NULL || head -> next == NULL) {
? ? ? ? // 少于兩個(gè)節(jié)點(diǎn)無需反轉(zhuǎn)
? ? ? ? return head;
? ? }
? ?
? ? ActList *pre = NULL;
? ? ActList *next = NULL;
? ? while (head != NULL) {
? ? ? ? next = head -> next;
? ? ? ? head -> next = pre;
? ? ? ?
? ? ? ? pre = head;
? ? ? ? head = next;
? ? }
? ?
? ? return pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode reverseList2(ListNode head)
{
if (head == null || head.next == null) return head;
ListNode newHeaderListNode = null;
while (head != null) {
ListNode tempListNode = head.next;
head.next = newHeaderListNode;
newHeaderListNode = head;
head = tempListNode;
}
return newHeaderListNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
方案四: 遞歸
ActList * reverseList4 (ActList * head) {
? ? if (head == NULL || head -> next == NULL) {
? ? ? ? // 少于兩個(gè)節(jié)點(diǎn)無需反轉(zhuǎn)
? ? ? ? return head;
? ? }
? ? ActList *newHead = reverseList4(head -> next);
? ?
? ? head -> next -> next = head;
? ? head -> next = NULL;
? ?
? ? return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head)
{
if (head == null || head.next == null) return head;
ListNode newHeaderListNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHeaderListNode;
}
