C++面试常见问题——04链表的逆序与合并

链表的逆序与合并

链表的逆序

已知一个链表的头指针为head，将该链表逆序。

#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
typedef struct Node Node;
Node* ReverseLinkList(Node* head){
Node* p1 = head;
Node* p2 = p1->next;
Node* p3 = p2->next;
p1->next = NULL;
if(p3->next != NULL){
p2->next = p1;
p1 = p2;
p2 = p3;
p3 = p3->next;
}
p2->next = p1;
head =p2;
return p2;
}
int main(){}

有序链表的合成

已知两个链表head1，head2各自有序，合并为一个新的有序链表

#include<iostream>
using namespace std;
struct Node{
int data;
Node* next;
};
typedef struct Node Node;
Node* MergeLinkList(Node* head1,Node* head2){
if(head1 == NULL){
return head2;
}
if(head2 ==NULL){
return head1;
}
Node* head;//新链表
Node* p1;//两个辅助结点
Node* p2;
if(head1->data <= head2->data){//先确定新链表的头结点
head = head1;
p1 = head1->next;
p2 = head2;
}
else{
head = head2;
p1 = head1;
p2 = head2->next;
}
Node* pcur = head;//辅助结点，用来确定新加入结点
while((p1 != NULL) && (p2 != NULL)){//两个链表都不为空时
if(p1->data <= p2->data){
pcur->next = p1;
pcur = p1;
p1 = p1->next;
}
else{
pcur->next = p2;
pcur = p2;
p2 = p2->next;
}
}
if(p1 == NULL){
pcur->next = p2;
}
else{
pcur->next = p1;
}
return head;
}
int main(){}