C++ 链表



链表


MaiziTest3.cpp : 定义控制台应用程序的入口点。


1.考点


数据结构掌握程度


2.代码


#include "stdafx.h"
 
struct Node
{
int data;
Node *next;
};
typedef struct Node Node;
//1、已知链表的头节点head,写一个函数把这个链表逆序。
//2、已知两个链表head1和head2各自有序,请把他们合并成一个依然有序的链表。(保留所有节点,即便大小相同)
 
//1
Node *ReverseList(Node *head)
{
if(head == NULL || head->next == NULL)
{
return head;
}
Node *p1 = head;
Node *p2 = p1->next;
Node *p3 = p2->next;
 
p1->next = NULL;//让链表头变为尾
while(p3 != NULL)
{
p2->next = p1;
p1 = p2;
p2 = p3;
p3 = p3->next;
}
p2->next = p1;//让链表尾变为头
head = p2;
return head;
}
//2
Node *Merge(Node *head1,Node *head2)
{
if(head1 == NULL)
{
return head2;
}
if(head2 == NULL)
{
return head1;
}
Node *head = NULL;
Node *p1 = NULL;
Node *p2 = NULL;
if(head1->data <= head2->data)
{
head = head1;
p1 = head1->next;
p2 = head2;
}
else
{
head = head2;
p2 = head2->next;
p1 = head1;
}
Node *pcurrent = head;
while(p1 != NULL && p2 != NULL)
{
if(p1->data <= p2->data)
{
pcurrent->next = p1;
pcurrent = p1;
p1 = p1->next;
}
else
{
pcurrent->next = p2;
pcurrent = p2;
p2 = p2->next;
}
}
if(p1 != NULL)
{
pcurrent->next = p1;
}
if(p2 != NULL)
{
pcurrent->next = p2;
}
return head;
}
int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}



课后作业


在2的基础上,这次要求用递归方法进行实现。



【本文由麦子学院独家原创,转载请注明出处并保留原文链接】

logo
© 2012-2016 www.maiziedu.com
蜀ICP备13014270号-4 Version 5.0.0 release20160127

您有狂欢嘉年华礼包未领取

客服热线 400-862-8862

回到顶部