.编写一个程序，有单链表的节点类型如下：
typedef struct node
{
struct node *
}
设计如下函数：
void create(Node *h):建立不带头节点的单链表h
int
.编写一个程序，有单链表的节点类型如下：
typedef struct node
{
struct node *
}
设计如下函数：
void create(Node *h):建立不带头节点的单链表h
int len(Node *h):返回不带头节点的单链表h的长度
void del(Node *h,int i):删除不带头节点的单链表h的第i个节点
void disp(Node *h):输出不带头节点的单链表h的所有节点值
其中：main函数如下：
void main()
{
create(head);
disp(head);
cout<<"链表长度：" <<len(head)<<
cout<<"删除第几个节点:";
del(head,i);
disp(head);
}
题目有点烂。 head没有任何值的时候就使用它是不合理的，所以我改了一下，
把 Node * 改成了Node *head=new N 在相关信息下，如果 head不指向任何值，把它做为参数是没有意义的。
typedef struct node
{
struct node *
}N
/*把node改成了Node*/
void create(Node *h){
static Node *
h->next=0;
current=h;
for(i=2;i<10;i++){
Node * temp= new N
temp->no=i;
temp->next=0;
current=current->next=
}
}
int len(Node *h){
int count=0;
Node *current=h;
while(cur...</10;i++){
>...
题目有点烂。 head没有任何值的时候就使用它是不合理的，所以我改了一下，
把 Node * 改成了Node *head=new N 在相关信息下，如果 head不指向任何值，把它做为参数是没有意义的。
typedef struct node
{
struct node *
}N
/*把node改成了Node*/
void create(Node *h){
static Node *
h->next=0;
current=h;
for(i=2;i<10;i++){
Node * temp= new N
temp->no=i;
temp->next=0;
current=current->next=
}
}
int len(Node *h){
int count=0;
Node *current=h;
while(current!=0){
current=current->
}
void disp(Node *h){
Node *current=h;
while(current!=0){
cout<no<<" ";
current=current->
void del(Node *h,int i){
Node *temp,*current=h;
if(ilen(h))
if(--i){
while(--i)
current=current->
temp=current->
current->next=temp->
void main()
{
Node *head=new N
create(head);
disp(head);
cout<<"链表长度：" <<len(head)<<
cout<<"删除第几个节点:";
cin>>i;
del(head,i);
disp(head);
}
其他答案（共1个回答）
中改变实参的值，以下函数的参数略有改变，声明了引用类型：
void create(Node *h); //楼主的声明
void create(Node *&h , int maxno); //修改后的声明
void del(Node *h,int i); //楼主的声明
void del(Node *&h,int i); //修改后的声明
另外，对于create(...
由于要在相关信息中改变实参的值，以下函数的参数略有改变，声明了引用类型：
void create(Node *h); //楼主的声明
void create(Node *&h , int maxno); //修改后的声明
void del(Node *h,int i); //楼主的声明
void del(Node *&h,int i); //修改后的声明
另外，对于create()还增加了一个参数：maxno，作用是指定链表节点的no成员的值。指定一个maxno后，创建出来的链表包含0~maxno之间所有整数的节点（max>=0，否则会创建空链表）。
由于没有装vc，以下程序在tc++3,0下调试通过：
//list.cpp
#include
typedef struct node
{
struct node *
} N
void create(Node *&h , int maxno); //建立不带头节点的单链表h，参数有所改动
int len(Node *h); //返回不带头节点的单链表h的长度
void del(Node *&h,int i); //删除不带头节点的单链表h的第i个节点（i从0起计算），参数有所改动
void disp(Node *h); //输出不带头节点的单链表h的所有节点值
void main()
{
create(head,3);
disp(head);
cout << endl << "链表长度：" << len(head) <<
cout << endl <<"删除第几个节点:";
del(head,i);
disp(head);
}
void create(Node *&h , int maxno)
{
if (maxno >= 0) //创建第一个节点
p = (Node *)malloc(sizeof(Node));
p->no = 0;
h = NULL; //参数表中声明h为Node指针的引用类型，所以可以通过形参改变实参的值
for(i=1 ; i<= i++) //创建后继节点
p->next = (Node *)malloc(sizeof(Node));
p->next->no =
p->next = NULL;
}
int len(Node *h)
{
int lencount = 0;
lencount++;
h = h-> //参数表中h没有被声明为引用类型，改变h的值不会改变实参的值
void del(Node *&h,int i)
{
Node *p , *q;
if (i<0 || h==NULL) //要删除的节点不存在，或链表空
if (i==0) //删除首节点
h = h-> //h是引用类型，改变它的值可以改变实参的值
for(j=1,p= j<=i && p!=NULL ; j++) //删除其它节点
if (p!=NULL)
q->next = p->
void disp(Node *h)
{
while(h!=NULL)
这样做试试：
先判断并处理插入位置为1的特殊情况，也就是插入的点会成为新的头结点。
再用指针q依次向后，停在第i个位置上，并在i-1的位置上用指针r定位。
包含头文件#include
SYSTEMTIME
获得系统时间就用
GetLocalTime( &st );
st.wYear,st.wMo...
#include "stdio.h"
struct point
struct point *
}LNode,*...
学习windows编程先。
我选了操作系统、编译原理的课，并且有两年的Borland C++编程经验之后，也要用一个月才初步掌握VC。
可以试试这个简单的方法:程序执行时,让用户输入一个整数(如1表示插入排序,2表示选择排序,3表示冒泡排序)选择使用哪种排序方法,然后根据用户输入的不同值执行不同...
答: 十二周nt检查，nt值2.0是不是不好
答: Project——settings，在General属性页中有一个Microsoft Foundation Classes的下拉列表框，选择Use MFC in...
答: Project——settings，在General属性页中有一个Microsoft Foundation Classes的下拉列表框，选择Use MFC in...
大家还关注
确定举报此问题
举报原因(必选)：
广告或垃圾信息
激进时政或意识形态话题
不雅词句或人身攻击
侵犯他人隐私
其它违法和不良信息
报告，这不是个问题
报告原因(必选)：
这不是个问题
这个问题分类似乎错了
这个不是我熟悉的地区
相关问答：123456789101112131415判断两个链表是否有公共节点的方法最简单的就是遍历到每个链表的最后一个节点，看他们是否是同一个节点：如果是同一个节点的话，那么两个链表肯定有公共节点：
解释：因为链表是线性结构，不想树那样的非线性分叉结构
从链表的定义，就知道：
typedef struct LNode{
struct LNode *
}LNode, *LinkL&
一个链表有唯一的一个后序节点：如果两个链表中出现了公共节点，那么从该点开始，后面的节点都是公共的，肯定链表的最后一个节点也是公共的。于是不管三七二十一，遍历到最后链表的一个节点，判断两个节点是不是同一个节点就可以了。
但是这里我们要返回第一个公共节点，所以还得寻去他法：
1.如果两个链表有长度一样，我们从第一个逐个遍历节点，再比较是不是同一个节点就可以了；
2.如果两个链表长度不一样，我们应该先让长的链表从表头&走& len1 - len2步（len1为list1的长度，len2为list2的长度），然后按照1中方法进行操作即可。
# include &stdio.h&
# include &malloc.h&
typedef struct LNode{
struct LNode *
}LNode, *LinkL
* 采用数组a[]来初始化链表，数组的长度为head指向了头节点。
LinkList CreatList(int a[], int length)
LinkList head = (LinkList)malloc(sizeof(LNode));
head-&next = NULL;
for (index = 0; index & index ++)
temp = (LinkList)malloc(sizeof(LNode));
temp-&data = a[index];
temp-&next = head-&
head-&next =
* 判断链表list1与链表list2是否相交，如果相交的话，就返回第一个相交点
* 注意相交的话，就是横着的Y字型
int isIntersect(LinkList list1, LinkList list2)
LinkList ptr1 = list1-&
LinkList ptr2 = list2-&
int len1 = getLength(list1);
int len2 = getLength(list2);
int step = len1 - len2;
if(step & 0)
//list1长，那么list1先走step；
for (index = 0; index & index ++)
ptr1 = ptr1-&
//list2长，那么list2先走
for (index = 0; index & -1 * index ++)
ptr2 = ptr2-&
while (ptr1 != NULL)
if (ptr1 == ptr2)
printf("the first intersection node is %d/n", ptr1-&data);
ptr1 = ptr1-&
ptr2 = ptr2-&
printf("there is no insection node between the two list");
int main()
int a4[] = {1,2,3,4,5};
LinkList list = CreatList(a4,5);
LinkList current = list-&
while (current-&next)
current = current-&
current-&next = list-&next-&
//公共点为4
int result1 = isLoop(list);
getLoopNode(list);
本文已收录于以下专栏：
相关文章推荐
题目：输入两个链表，找出它们的第一个公共节点。链表的定义如下：
struct ListNode
ListNode *m_pN
题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
struct ListNode
单链表判断有无公共节点是个比较有趣的问题。这里所说的公共节点指的是完全相同的节点，不同与一般意义上的节点元素相同。相交单链表简单的都会是如下形式（有环除外）：
http://m.blog.csdn.net/blog/z/9734179
当用new操作符调用一个函数时,就会创建一个新的javascript对象.接着,该函数会作...
题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
struct ListNode
1、两个单链表（无序），寻找第一个公共节点（如何判断单链表存在环）。
2、两个单链表（无序），寻找第一个公共节点（如何判断单链表存在环）。
3、如过两个链表可能有环，如何判断两个链表是否相交？以及找到...
输入两个链表，找出它们的第一个公共的节点。
碰到这种题的时候千万不要用挨个遍历的方法，时间复杂度高
对于两个有相同节点的链表的形状一定是Y。而不是X。然后还可能一个链表长一个链表短，我们可...
输入两个链表，找出它们的第一个公共结点。
两个有公共节点的链表，具有这样的特点：单向链表的节点的的属性有节点的值，它指向的下一个节点。所以当有一个公共节点时，不仅值相同，它们指向的下一个节...
输入两个链表，找出它们的第一个公共结点。
画图会发现如果二者有公共结点，则公共节点后面的节点也都是公共节点。用两个辅助栈，将两个链表从头分别压入栈，最后二者出栈，最后一个相同的出栈...
输入两个链表，找出他们的第一个公共节点。
解法一：O(mn)
在第一个链表上顺序遍历每个节点，每遍历到一个节点的时候，在第二个链表上顺序遍历每个节点，找到一样的节点，即为第一个公...
他的最新文章
讲师：李江龙
讲师：司徒正美
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)今天看啥 热点：
判断两个单向链表是否有相交，并找出交点。，相交交点
若相交，则两个链表呈Y型，最后一个结点肯定相同；找交点，则用长的链表减去短的，从与短的链表长度相等处开始，两个链表每次移动一个结点，直到相交则是交点。
NODE* FindNode(NODE* pHead1, NODE* pHead2)
NODE* p1 = pHead1;
NODE* p2 = pHead2;
int i = 1, j = 1, k = 0, f = 0;
if(pHead2 == NULL || pHead2 == NULL)
return NULL;
while(p1-&next != NULL)
while(p2-&next != NULL)
if(p1 != p2)
return NULL;
p1 = pHead1;
p2 = pHead2;
f = fabs(i, j);
for(k=0; k&f; k++)
while(p1 != p2)
return p1;
for(k=0; k&f; k++)
while(p1 != p2)
return p1;
如果两个链表有公共节点，那么该节点中的next指针也是共用的，因此，这两个链表自此开始的next，以及next的next……都是共用的。一直到tail节点。故判断相交的方法很简单，找到各自的tail节点的地址，比较是否相等。if (pTailNode1 == pTailNode2)相交。
微软面试题。思路：用两个指针，pSlow，pFast，就是一个慢一个快慢的一次跳一步，快的一次跳两步，什么时候快的追上慢的了（就是pSlow == pFast || pSlow-&next == pFast），就表示有环。
相关搜索：
相关阅读：
相关频道：
&&&&&&&&&&&&&&&&
WEB编程教程最近更新两链表求公共节点 - Felix Fang - 博客园
随笔 - 88, 文章 - 63, 评论 - 60, 引用 - 0
其实这道题目早在剑指Offer上就已经出现过，参见以前的，但后来July前辈也有讲过类似问题，对比之下，之前的解法还不够全面，没有考虑到所有情况，这篇文章把这道题目作一个梳理。
题目总结起来是这样：
输入两个链表，判断它们是否有公共节点，返回bool。
引申：找出它们的第一个公共节点的指针，如果没有公共节点则返回NULL。
链表的定义如下：
struct ListNode{
ListNode(int x) : val(x), next(NULL) {};
输出函数：
bool JudgeCommonListNode(ListNode* head1, ListNode* head2){
ListNode* FindFirstCommonListNode(ListNode* head1, ListNode* head2){
} //引申，求第一个公共节点
首先需要考虑空指针输入，有一个输入为NULL，就不会有交点。
寻找两链表的第一个交点，简便的做法是求出两链表长度差diff后，让长的链表先走diff步，然后依次比较两链表节点，若相同则返回。
但这一个思路的前提是：两个链表都不含环。
因此，在考虑完空指针后，需要检验两个链表是否含有环。
(1) 若一个有环一个无环，则肯定没有交点。
(2) 若都无环，可以用上面的思路求出第一个交点；如果只要求返回bool，则比较一下两链表的尾节点是否相等即可。
(3) 两链表都含有环的情况下，如果只需要返回bool值，我们就检验其中一个链表的环入口是否在另一个链表的环上，在环上就返回true，表明相交，不在环上返回false。
如果要返回第一个交点呢？这时候我们可以分情况考虑：如果两个链表都是&勺型&，所谓勺型，就是指不是纯的环链表。那这两个勺型链表如果有交点，环部分肯定是已经百分百重叠了，第一个交点只能出现在&勺柄&上，既然是勺柄，自然就无环啦，因此，上面那个求两个无环链表的第一个交点的方法有可以拿来用了~
如果两个链表都有环，而且至少有一个是纯环链表，那么如果有交点，这个纯环链表必然所有节点都和另一个链表的环部分重合。此时，我们把那个纯环链表的输入节点(假设是head1)看作第一个交点，因此，只需要验证一下head1是否在另一个链表的环上即可。在的话就返回head1，不在就返回NULL。
因此这道题目其实并不简单，它包含&判断链表是否含有环&，&求环入口节点&，&求两条无环链表的第一个交点& 三个子问题。
这里给出引申问题，也就是求第一个交点的题目的代码，辅助函数traverse 的功能包含判断是否有环，返回环入口节点(无环则返回NULL)，以及求头结点距离环入口节点(有环情况)或者尾节点(无环情况)的长度，这个长度被存在len变量里。
在判断是否有环的过程中，需要注意单节点环链表的情况。
ListNode* traverse(ListNode* head, int &len, bool &circled){
ListNode* p1 = head -& next, *p2 = head -&
int step = 1;
for(; p2 != NULL; ++step, p1 = p1 -& next, p2 = p2 -& next){
p2 = p2 -&
if(!p2 || p1 == p2) break;
//用len记录链表长度
circled = false;
return NULL;
}else{//有环
circled = true;
len = 0; //用len记录头结点到环入口距离
for(p1 = p1 != p2; p1 = p1 -& next, p2 = p2 -& next, ++len);
return p1;
ListNode* FindFirstCommonListNode(ListNode* head1, ListNode* head2){
if(!head1 || !head2) return NULL;
if(head1 == head2) return head1;
int len1 = 0, len2 = 0; bool cc1 = false, cc2 = false;
ListNode* CcleEnt1 = traverse(head1, len1, cc1);
ListNode* CcleEnt2 = traverse(head2, len2, cc2);
if((!cc1 && cc2) || (cc1 && !cc2)) return NULL;
//若一个有环，一个无环，则肯定没有交点
if(len1 & 0 && len2 & 0){
//当两链表都无环，或者都有环且首节点都不在环上时
ListNode *st1 = (len1 & len2 ? head1 : head2);
ListNode *st2 = (len1 & len2 ? head2 : head1);
ListNode *cce1 = (len1 & len2 ? CcleEnt1 : CcleEnt2);
ListNode *cce2 = (len1 & len2 ? CcleEnt2 : CcleEnt1);
for(int i = 0; i & (len1 - len2 & 0 ? len1 - len2 : len2 - len1); ++i, st1 = st1 -& next);
for(; st1 != cce1 && st2 != cce2 && (st1 != st2); st1 = st1 -& next, st2 = st2 -& next);
if(st1) return st1;
return NULL;
//len1, len2 中有一个为0 说明其中至少有一条链表是纯环链表。
ListNode *st1 = (len1 == 0 ? head1 : head2); //选择那个纯环链表的head，验证它是否在另一个链表的环上，在的话它就是第一个交点，不在的话就没有交点。
ListNode *st2 = (len1 == 0 ? head2 : head1);
ListNode *p = st2 -&
for(; p != st2 && p != st1; p = p -& next);
if(p == st1) return st1;
return NULL;
带测试用例的代码：
#include &iostream&
using namespace
struct ListNode{
ListNode(int x) : val(x), next(NULL) {};
ListNode* CreateListNode(int value)
ListNode* pNode = new ListNode(value);
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)
if(pCurrent == NULL)
cout && "Error to connect two nodes.\n";
pCurrent -& next = pN
ListNode* traverse(ListNode* head, int &len, bool &circled){
ListNode* p1 = head -& next, *p2 = head -&
int step = 1;
//cout && "---------\n";
for(; p2 != NULL; ++step, p1 = p1 -& next, p2 = p2 -& next){
//只有一个节点的环链表
//cout && "p2: " && p2 -& val &&
p2 = p2 -&
if(!p2 || p1 == p2) break;
//cout && "---------\n";
//用len记录链表长度
circled = false;
cout && "circled: "
&& (circled ? "Yes" : "No")
&& "; length: " && len &&
return NULL;
}else{//有环
circled = true;
len = 0; //用len记录头结点到环入口距离
for(p1 = p1 != p2; p1 = p1 -& next, p2 = p2 -& next, ++len);
cout && "circled: "
&& (circled ? "Yes" : "No")
&& "; length: " && len &&
return p1;
ListNode* JudgeCommonListNode(ListNode* head1, ListNode* head2){
if(!head1 || !head2) return NULL;
if(head1 == head2) return head1;
int len1 = 0, len2 = 0; bool cc1 = false, cc2 = false;
ListNode* CcleEnt1 = traverse(head1, len1, cc1);
ListNode* CcleEnt2 = traverse(head2, len2, cc2);
if((!cc1 && cc2) || (cc1 && !cc2)) return NULL;
//若一个有环，一个无环，则肯定没有交点
if(len1 & 0 && len2 & 0){
//当两链表都无环，或者都有环且首节点都不在环上时
ListNode *st1 = (len1 & len2 ? head1 : head2);
ListNode *st2 = (len1 & len2 ? head2 : head1);
ListNode *cce1 = (len1 & len2 ? CcleEnt1 : CcleEnt2);
ListNode *cce2 = (len1 & len2 ? CcleEnt2 : CcleEnt1);
for(int i = 0; i & (len1 - len2 & 0 ? len1 - len2 : len2 - len1); ++i, st1 = st1 -& next);
for(; st1 != cce1 && st2 != cce2 && (st1 != st2); st1 = st1 -& next, st2 = st2 -& next);
if(st1) return st1;
return NULL;
//len1, len2 中有一个为0 说明其中至少有一条链表是纯环链表。
ListNode *st1 = (len1 == 0 ? head1 : head2); //选择那个纯环链表的head，验证它是否在另一个链表的环上，在的话它就是第一个交点，不在的话就没有交点。
ListNode *st2 = (len1 == 0 ? head2 : head1);
ListNode *p = st2 -&
for(; p != st2 && p != st1; p = p -& next);
if(p == st1) return st1;
return NULL;
/**---------测试代码----------*/
ListNode* CreateList1(){
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
return pNode1;
ListNode* CreateCc1(){
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
ConnectListNodes(pNode5, pNode2);
return pNode1;
int main(){
ListNode* head1 = CreateList1();
ListNode* head2 = CreateCc1();
ListNode* res = JudgeCommonListNode(head1, head2);
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode3, pNode2);
ListNode* res = JudgeCommonListNode(pNode1, pNode3);
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ConnectListNodes(pNode1, pNode2);
ListNode* res = JudgeCommonListNode(pNode1, pNode2);
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ConnectListNodes(pNode1, pNode1);
ConnectListNodes(pNode2, pNode2);
ListNode* res = JudgeCommonListNode(pNode1, pNode2);
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ListNode* pNode6 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
ConnectListNodes(pNode6, pNode3);
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ListNode* pNode6 = CreateListNode(6);
ListNode* pNode7 = CreateListNode(7);
ListNode* pNode8 = CreateListNode(8);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
ConnectListNodes(pNode5, pNode6);
ConnectListNodes(pNode6, pNode3);
ConnectListNodes(pNode7, pNode8);
ConnectListNodes(pNode8, pNode2);
//ListNode* res = JudgeCommonListNode(pNode1, pNode7);
//ListNode* res = JudgeCommonListNode(pNode7, pNode3);
ListNode* res = JudgeCommonListNode(pNode1, pNode5);
if(res) cout && "First overlap is: " && res -& val &&
else cout && "Not overlap" &&
带有Main函数的代码
