链表逆转输出
方案一：head 作为已知首节点，最后节点指向null， 使用三个指针便利链表，逐个节点进行反转
实现代码：
struct ActList {
ActList * next;
};
ActList * reverseList(ActList * head) {
if (head == NULL || head -> next == NULL) {
// 少于两个节点无需反转
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
方案二： 对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾
代码：
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;//相当于成环
head=p->next->next;//新head变为原head的next
p->next->next=NULL;//断掉环
return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
方案三：循环
ActList * reverseList3 (ActList * head) {
if (head == NULL || head -> next == NULL) {
// 少于两个节点无需反转
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) {
// 少于两个节点无需反转
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;
}
