和面试官对两道数据结构算法题持不同意见，望各位前辈给予指教，在此多谢各位了！
--------------------编程问答-------------------- 先不说算法，感觉你这个代码定义有点问题1、q定义时无需new
2、各变量定义类型应该是链表类型LinkList，而不是Node
面试官的方法：
从链表的开始循环到结束，然后从最后一个结点开始往前依次交换结点。
================
单向链表，怎么往前依次呢？把这个解决了算法就简单了
--------------------编程问答-------------------- 要是C++用指针，这算法就简单了
每个链表的Next节点指针-1就可以了 --------------------编程问答-------------------- 每个链表的Next节点指针等于当前节点的指针-1就可以了 --------------------编程问答-------------------- Next节点-1？链表又不是顺序表，-1能找到前一个元素？ --------------------编程问答-------------------- Public void ReversLinkList(LinkList H)
{
Node p=H.Next;
Node q= new Node;
H.Next= null;
While(p!= null)
{
q=p;
p=p.Next;
q.Next=H.Next;
H.Next=q;
}
}
支持你的，我也刚看到这个算法，时间复杂度O（n），我没看出面试官的算法比你的好在哪，不过人家既然是面试官，你又想某的这个职位当时最好是按人家的思路来，呵呵，其他可以以后再说嘛！ --------------------编程问答--------------------
-1是指指针-1
C++链表指针在内存里是顺序里，-1就代表上一个节点的地址
--------------------编程问答-------------------- --------------------编程问答-------------------- 这个面试官是2B,单链表上哪从后往前找 --------------------编程问答-------------------- 这种不懂装懂，或说懂一点装全懂，固执听不进别人的方法的技术人员，是很难一起共事的。
LZ还是不要去了，单向链表能从后往回找么？是不是还得用栈呀！
另外LZ应该反问一句，两个链表如果其中一个有环怎么办？还不得死循环了！
--------------------编程问答-------------------- 虽然不懂 链表 支持楼主 --------------------编程问答--------------------
c++我学艺不精，但觉得不太对，链表本就是空间上不连续的，指针怎能-1找到上一个，指针的-1操作表示向前偏移一个指针指向类型的长度。专门做了个例子。发现的确-1不行。
// VCConsole01.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
template <typename T>
class LinkListItem
{
public:
LinkListItem(T d)
{
Data = d;
}
public:
T Data;
LinkListItem* pNext;
};
template <typename T>
class LinkList
{
public:
LinkList()
{
pHead = pEnd = NULL;
}
void Add(T data)
{
if (pHead)
{
pEnd->pNext = new LinkListItem<T>(data);
pEnd = pEnd->pNext;
}
else
{
pHead = new LinkListItem<T>(data);
pEnd = pHead;
}
}
public:
LinkListItem<T>* pHead;
LinkListItem<T>* pEnd;
};
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
LinkList<int> list;
list.Add(1);
list.Add(2);
list.Add(3);
list.Add(4);
LinkListItem<int>* pPrevous = list.pEnd-1;
cout<<pPrevous->Data;
cin.get();
return 0;
}
另外，楼主代码运行结果是错误的。 --------------------编程问答-------------------- --------------------编程问答-------------------- 比较笨的方法用List数组，不过貌似这个有点违背链表算法
public void ReversLinkList(LinkList H)--------------------编程问答-------------------- 13楼的写法估计就是那个面试官所期望的。时间复杂度是O(n*2) --------------------编程问答--------------------
{
if(H==null)
return;
LinkList N = H.Next; //下一个节点，用于while循环
List<LinkList> lstLink = new List<LinkList>();
lstLink.Add(H);
while (N != null)
{
lstLink.Add(N);
N = N.Next;
}
//反转
for (int i =0;i<lstLink.Count/2;i++)
{
LinkList T = lstLink[i];
lstLink[i] = lstLink[lstLink.Count - 1 - i];
lstLink[lstLink.Count - 1 - i] = T;
}
//lstLink里的各元素就是反转后的节点
}
你用单向链表做个环看看？ --------------------编程问答-------------------- 当我没有说。。。。。汗了！ --------------------编程问答-------------------- 我算法太菜了。所以对这种简单的也想试试。楼主的算法的确不错。不过调用方法不同。反正没测试出正确结果。就按想法，继续写的正确的，规范下命名。方便阅读。
--------------------编程问答-------------------- while(*p++=*p1++); --------------------编程问答-------------------- p1=*P++;
static void Main(string[] args)
{
MyLinkList<int> testList = new MyLinkList<int>();
testList.Add(1);
testList.Add(2);
testList.Add(3);
testList.Add(4);
testList.MyReverse2();
foreach (var item in testList)
{
Console.WriteLine(item.Data);
}
Console.ReadKey();
}
public class MyLinkList<T> : IEnumerable<MyLinkListItem<T>> where T : new()
{
public MyLinkListItem<T> Head;
public MyLinkListItem<T> End;
public void Add(T item)
{
if (Head == null)
{
Head = new MyLinkListItem<T>(item);
End = Head;
}
else
{
End.next = new MyLinkListItem<T>(item);
End = End.next;
}
}
//使用数组方式保存然后逆序的设置
public void MyReverse()
{
List<MyLinkListItem<T>> buf = new List<MyLinkListItem<T>>();
MyLinkListItem<T> p = Head;
while (true)
{
if (p == null) break;
buf.Add(p);
p = p.next;
}
Head = buf[buf.Count - 1];
Head.next = buf[buf.Count - 2];
p = Head;
for (int i = buf.Count - 1; i > 0; i--)
{
p.next = buf[i - 1];
p = p.next;
}
p.next = null;
}
//循环一次，交换
public void MyReverse2()
{
MyLinkListItem<T> previous = Head;
MyLinkListItem<T> current = Head.next;
MyLinkListItem<T> temp = null;
previous.next = null;
while (current != null)
{
temp = current;
current = current.next;
temp.next = previous;
previous = temp;
}
Head = previous;
}
public IEnumerator<MyLinkListItem<T>> GetEnumerator()
{
MyLinkListItem<T> p = Head;
while (true)
{
if (p == null) break;
yield return p;
p = p.next;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
}
public class MyLinkListItem<T> where T : new()
{
public T Data;
public MyLinkListItem<T> next = null;
public MyLinkListItem()
{
Data = new T();
}
public MyLinkListItem(T t)
{
Data = t;
}
public override string ToString()
{
return Data.ToString();
}
}
P1=p->Next; --------------------编程问答-------------------- 链表反转
from my blog
http://www.cnblogs.com/Peter-Zhang/articles/1785554.html
第二题：
链表没说是顺序的，所以你的思路有问题
比如
1）
link1 2 3
link2 3 4
根据你的“最后的结点相同则有相同结点，否则没有”得没有
2）
link1 4 7
link2 1 3 5 7
根据：“比较两个链表的长度M和N(此处假设M>N)，然后对于较长的那个链表，指针次后移直到 M-N 的位置（因为多出来的结点肯定不是相同结点），然后再去循环比较。”得出没有。
--------------------编程问答-------------------- Peter同志，我估计面试第二题的原意应该指的不是值相同，而是同一个引用，也就是说是那种Y型的链表。这样的话LZ答的就没问题了。
--------------------编程问答-------------------- 路过参观学习。 --------------------编程问答-------------------- 相同的结点,应该是值和Next都相同吧,如果单纯的比较值的话,那肯定两个方法都不对
如果是比值和Next的话,由"link2 3 4"可推出,3后面肯定有4,"link1 2 3"肯定是"link1,2,3,4"
--------------------编程问答-------------------- 我试了下,楼主第一题的方法正确,
class Program--------------------编程问答-------------------- 他写的next。你的是Head。没说思路不对。你直接用他的不改试试？ --------------------编程问答--------------------
{
class Node
{
public int Value = 0;
public Node Next = null;
}
class LinkList
{
public Node Head = null;
}
static void Main(string[] args)
{
LinkList list = new LinkList();
Node node = new Node();
node.Value = 0;
list.Head = node;
for (int i = 1; i < 15; i++)
{
node.Next = new Node();
node.Next.Value = i;
node = node.Next;
}
node = list.Head;
while (node != null)
{
Console.WriteLine(node.Value.ToString());
node = node.Next;
}
Console.WriteLine("=============================");
ReversLinkList(list);
node = list.Head;
while (node != null)
{
Console.WriteLine(node.Value.ToString());
node = node.Next;
}
Console.ReadKey();
}
static void ReversLinkList(LinkList H)
{
Node p = H.Head;
Node q = null;
H.Head = null;
while (p != null)
{
q = p;
p = p.Next;
q.Next = H.Head;
H.Head = q;
}
}
以他的代码,应该H.Next是链表的头
可能是这样定义的:
class LinkList
{
public Node Next = null;
}
否则,肯定是 class LinkList:Node {};
如果是第二种的话,它应该传入LinkList* H,否则无法修改H本身
--------------------编程问答-------------------- 所以说不知道他调用方法。无法用他代码测试通过。 --------------------编程问答-------------------- 第一题，楼主的方法觉得不错啊，我也没明白面试官的意思
第二题，没明白楼主的意思 --------------------编程问答-------------------- 现在尤其是外包公司都在学习微软的面试，爱考算法，其实面试官水平也就那么回事，还在那装B呢 --------------------编程问答-------------------- --------------------编程问答--------------------
您真的是闲的慌啊 --------------------编程问答--------------------
对，我想面试官也是想要我写这个吧，让人无语的是他觉得这个方法很好，而觉得我用了很笨的方法。。。
--------------------编程问答--------------------
非常感谢！握手：） --------------------编程问答--------------------
多谢理解，是指引用的。。 --------------------编程问答-------------------- 其实这个方法最大的问题，除了要跑两遍之外，其空间复杂度是O(n)的，而反转链表的标准方法空间是O(1)的！
--------------------编程问答-------------------- 楼主你觉得你的思路确实有问题，关于单向linkedlist反转，我也没看懂你的代码。
要是我，我会这样做：
依次循环第一个链表，将每个结点插入到第二个列表第0个位置（表头），完成之后，看第二个链表，不是反转了？
linkedlist就是在头或中间插入结点很方便，性能也没啥损失。
求两个单链表是否有相同结点？如果有相同结点，返回第一个结点
暂时觉得只能做一个m*n的双层循环了，暂时没想到啥好办法。 --------------------编程问答-------------------- 好文收藏 --------------------编程问答--------------------
时间复杂度应该为O(n).
--------------------编程问答-------------------- 哈哈，来赚积分
--------------------编程问答-------------------- --------------------编程问答-------------------- --------------------编程问答--------------------
我也觉得lz至少写的含糊，面试官 又不会像 jointan 一样来迁就你，为你着想。 --------------------编程问答-------------------- 学习学习 --------------------编程问答-------------------- 都是高手。。。来学习 --------------------编程问答-------------------- 关于第一题，建议看看 严奶奶写的《数据结构》，清华大学出版社的，上面有一程序，用来构造单向链表的，或许会有帮助。把已经存在的链表重新构造出来，花费的时间是链表的长度。
关于第二题，我觉得面试官说对了。你说的（1）很直观。你说的（2）可以找出一个反例，假设两个链表只有第一个节点相交，短链表长度只有1个节点，长链表长度有100个节点，按照你的思路找不到。
--------------------编程问答-------------------- --------------------编程问答-------------------- 先不说算法，感觉你这个代码定义有点问题
1、q定义时无需new
2、各变量定义类型应该是链表类型LinkList，而不是Node
面试官的方法：
从链表的开始循环到结束，然后从最后一个结点开始往前依次交换结点。
================
单向链表，怎么往前依次呢？把这个解决了算法就简单了
--------------------编程问答--------------------
你这不对吧 LZ都说了引用也相同 那必然是一个Y型 LZ的思路很正确啊 --------------------编程问答-------------------- 学习学习
--------------------编程问答-------------------- --------------------编程问答-------------------- 链表应该在地址空间上不是连续的吧。 Node q= new Node; 这个地方不应该用new --------------------编程问答-------------------- 草，都是装逼，真正懂算法的有几人 --------------------编程问答-------------------- 都不太理解数据结构了。 --------------------编程问答--------------------
第一题：楼主的方法绝对正确
直接将头结点设置为尾结点，让他的地址枢为NULL.然后循环往它前面添加后边的结点，很简单很有效的
顶 --------------------编程问答-------------------- “2． 比较两个链表的长度M和N(此处假设M>N)，然后对于较长的那个链表，指针次后移直到 M-N 的位置（因为多出来的结点肯定不是相同结点），然后再去循环比较。”
不对吧，为什么多出来的结点会不相同呢，你是不想的是结点的地址框不同，题目可能意思是值要相同。 --------------------编程问答-------------------- 第一题：
怎么看，你的算法都是正确的，而且是很简单、很清楚。真想不出那个面试官还能给出什么更好的算法，有的话就拿出来晒晒嘛
第二题：
我认为，你的算法（去掉多余的头部，并排走着找）和他的算法（从后向前找）都是对的，虽然他用来否定你的理由并不准确，但你的算法相对来说的确是多了一个不必要的环节，还是他的方法好一点。 --------------------编程问答-------------------- 楼层太高了，只看了几个帖子。说说我的看法：
招聘一个程序员不一定要看他写的代码如何花哨，因为许多东西是靠事后测试来优化的。因此首先看思路。也许lz的问题不在于他是否写对了代码，而也许在于它但是始终不愿意去沉下心来听别人。
lz的代码显然有滥用变量混淆意义的嫌疑。关于反转，我们写算法就是：
static Node 反转(Node head)
{
return 放到头部(head, null);
}
static Node 放到头部(Node a, Node b)
{
if (a == null)
return b;
var next = a.Next;
a.Next = b;
return 放到头部(next, a);
}
然后有闲工夫的时候（并且测试也证明确实值得去优化的时候）才去优化，例如修改为：
static Node 反转(Node head)
{
return 放到头部(head, null);
}
static Node 放到头部(Node a, Node b)
{
begin:
if (a == null)
return b;
var next = a.Next;
a.Next = b;
b = a;
a = next;
goto begin;
}
因此就算这两个程序都写出来了，如果程序员纠结于第一个程序，此程序员也是存在一个严重的影响团队开发的问题的。 --------------------编程问答-------------------- 我说过了，就算我写的两个代码都写出来了，如果纠结于第一个也成问题（注意这不是承认或者不承认编程的问题，而是看一个人品的问题）。
何况，看第一个算法就明白，确实是交换两个Node的意思。lz当时没有去理解并不算什么大事，真正的大事可能是lz当时的某个态度。 --------------------编程问答-------------------- sorry，上面两遍都写错了，
如果纠结于第一个也成问题 --> 如果纠结于第二个也成问题
因为第一个是算法，而第二个只是优化。面试官跟lz就是在讨论简洁清晰的算法，而lz脑筋中只有一个繁琐的东西盘旋。 --------------------编程问答-------------------- 对于第二题，诚如55楼所指出的，对于什么是“相同结点”的理解，可能影响会很大。
理解1：两个结点自身的value相等，而且next也指向“相同结点”；
理解2：两个结点自身的value相等。
现在我们不知道原题的准确描述是什么（也许本来就没有准确描述），但考虑到面试官肯定了LZ所说的第1点，看来他应该是按照“理解1”来理解的。 --------------------编程问答-------------------- 我想强调的是，写算法要清晰，不要因为纠结而繁琐。如果你给出递归的写法，再跟lz去论理（我不知道你说的“然后从最后一个结点开始往前依次交换结点”是否是原话）。如果你拿出一个拼凑起来的代码，就算它很高效，也缺乏说服力。在面试时，一个问题上的注意力只有几分钟，一个不会把握这几分钟的程序员就会出局。 --------------------编程问答-------------------- 如果lz你给出递归的写法，再跟面试官去论理，它会有效地在这几分钟内第一分钟就理解。而你把着几分钟搞得毫无效率，即使事后你又回来写出了代码并且觉得它虽然很乱但是很好，你能让面试官再面试你一次吗？ --------------------编程问答-------------------- 事实上，从算法上说，这个题目确实可以这样描述：链表a要反转，就是首先将链表a上刨除最后一个节点的其它结点的链接反转，然后将最后一个节点的next指向它。
但是这只是一般的思路，需要进行优化。首先分析结构从而可以直接将非尾递归改为尾递归（既我所写的第一段代码），然后可以直接把尾递归转换为迭代。
这就好像我们设计软件，我让你用c#、用3行代码写出一个程序来，我要考察的是设计能力（只不过是用代码而不是口头忽悠），我只有1分钟时间，而你偏给我写个c代码并且非要50分钟时间来争论编程而不是设计问题，这已经很说明问题了。如果你认为面试官的思路很一般，也一定要用对的方式来说。（当然，一头雾水什么都做不出来的除外） --------------------编程问答-------------------- 好棒的帖子 --------------------编程问答-------------------- 不错学习了 --------------------编程问答-------------------- lz的思路没错，我到ms和nokia面试时就遇到过这两道题，而且我的思路和lz是一样的，最后面试官都说答案是对的。
1、第一题面试官问为何不用递归（即你说的找到最后在逆回来），其实我之前我没做过单链表逆转，这只是当时想出的答案，面试官倒是提醒了我，我当时回答就是在链表长度未知的情况下，用递归不合适
2、其实第二题也是用递归，可惜我当时没做过，想的思路和lz是一样的，所以还是说递归不合适，呵呵。 --------------------编程问答-------------------- 这个要顶一下啊！ --------------------编程问答--------------------
这里人多，比较热闹好玩。
我写了个C语言版的，也来凑热闹！！！
--------------------编程问答--------------------
// 反转单向链表 (C语言版)
#include <stdio.h>
#include <stdlib.h>
#define N 16
struct LinkList
{
int nData;
struct LinkList* pNext;
};
struct LinkList* GetCreateLinkList(void)
{
struct LinkList* pHead = NULL;
struct LinkList* pList = NULL;
struct LinkList* pNew = NULL;
int i = 0;
pHead = pList = (struct LinkList*) malloc( sizeof(struct LinkList) );
pList->nData = 0;
while( ++i < N )
{
pNew = (struct LinkList*) malloc( sizeof(struct LinkList) );
pNew->nData = i;
pList->pNext = pNew;
pList = pList->pNext;
}
pList->pNext = NULL;
return pHead;
}
void printList(struct LinkList* pList)
{
puts("\n----------------------------");
while( pList )
{
printf("%d ", pList->nData);
pList = pList->pNext;
}
putchar('\n');
}
void DelLinkList(struct LinkList* pList)
{
struct LinkList* pDel = NULL;
while( pList )
{
pDel = pList;
pList = pList->pNext;
free( pDel );
}
}
struct LinkList* GetReversLinkList(struct LinkList* pHead)
{
struct LinkList* pList = NULL;
struct LinkList* pTmp = NULL;
struct LinkList* pRight = NULL;
if( !pHead )
{
return NULL;
}
pList = pHead;
if( !(pList = pList->pNext) )
{
return pHead;
}
pTmp = pList->pNext;
pList->pNext = pHead;
pHead->pNext = NULL;
while( pTmp )
{
pRight = pTmp->pNext;
pTmp->pNext = pList;
pList = pTmp;
pTmp = pRight;
}
return pList;
}
int main(void)
{
// Test
{
struct LinkList* pList = NULL;
pList = GetCreateLinkList();
printList(pList);
pList = GetReversLinkList(pList);
printList(pList);
DelLinkList(pList);
pList = NULL;
}
return 0;
}
--------------------编程问答-------------------- 。。。。。have a look --------------------编程问答-------------------- 吩咐是艰苦奋斗减肥阿的副经理等 --------------------编程问答-------------------- --------------------编程问答-------------------- while( pIntersect )
// 获取两个单向链表的第一个相交结点 (C语言版)
#include <stdio.h>
#include <stdlib.h>
#ifndef BOOL
// {
#define BOOL int
#define FALSE 0
#define TRUE 1
// }
#endif
struct LinkList
{
int nData;
struct LinkList* pNext;
};
struct LinkList* CreateListTmp(struct LinkList** pTail, int i, int nEnd)
{
struct LinkList* pHead = NULL;
struct LinkList* pList = NULL;
struct LinkList* pNew = NULL;
pHead = pList = (struct LinkList*) malloc( sizeof(struct LinkList) );
pList->nData = i;
while( ++i < nEnd )
{
pNew = (struct LinkList*) malloc( sizeof(struct LinkList) );
pNew->nData = i;
pList->pNext = pNew;
pList = pList->pNext;
}
pList->pNext = NULL;
*pTail = pList;
return pHead;
}
BOOL Create2IntersectList(struct LinkList** pHead1, struct LinkList** pHead2)
{
struct LinkList* pTail1 = NULL;
struct LinkList* pTail2 = NULL;
struct LinkList* pTmp = NULL;
if( !(pHead1 && pHead2) )
{
return FALSE;
}
*pHead1 = CreateListTmp(&pTail1, 1, 11);
*pHead2 = CreateListTmp(&pTail2, -10, 0);
pTail1->pNext = pTail2->pNext = CreateListTmp(&pTmp, 100, 110);
return TRUE;
}
void printList(struct LinkList* pList)
{
puts("\n----------------------------");
while( pList )
{
printf("%d\t", pList->nData);
pList = pList->pNext;
}
putchar('\n');
}
// 获取两个单向链表的第一个相交结点
//
struct LinkList* GetFirstIntersectNode(struct LinkList* pHead1, struct LinkList* pHead2)
{
int n = 0;
struct LinkList* pList1 = pHead1;
struct LinkList* pList2 = pHead2;
int nNum1 = 1;
int nNum2 = 1;
if( !(pHead1 && pHead2) )
{
return NULL;
}
while( pList1->pNext )
{
pList1 = pList1->pNext;
++nNum1;
}
while( pList2->pNext )
{
pList2 = pList2->pNext;
++nNum2;
}
if( pList1 != pList2 )
{
return NULL;
}
////////////////////////////////////////
if( nNum1 > nNum2 )
{
n = nNum1 - nNum2;
pList1 = pHead1;
pList2 = pHead2;
}
else
{
n = nNum2 - nNum1;
pList1 = pHead2;
pList2 = pHead1;
}
while( n-- )
{
pList1 = pList1->pNext;
}
while( pList1 != pList2 )
{
pList1 = pList1->pNext;
pList2 = pList2->pNext;
}
return pList1;
}
BOOL Free2IntersectList(struct LinkList* pList1,
struct LinkList* pList2,
struct LinkList* pIntersect)
{
struct LinkList* pDel = NULL;
if( !(pList1 && pList2 && pIntersect) )
{
return FALSE;
}
while( pList1 != pIntersect )
{
pDel = pList1;
pList1 = pList1->pNext;
free( pDel );
}
while( pList2 != pIntersect )
{
pDel = pList2;
pList2 = pList2->pNext;
free( pDel );
}
while( pIntersect )
{
pDel = pIntersect;
pIntersect = pIntersect->pNext;
free( pDel );
}
return TRUE;
}
int main(void)
{
// Test
{
struct LinkList* pIntersect = NULL;
struct LinkList* pList1 = NULL;
struct LinkList* pList2 = NULL;
Create2IntersectList(&pList1, &pList2);
printList(pList1);
printList(pList2);
pIntersect = GetFirstIntersectNode(pList1, pList2);
printf("\nTest:");
printList( pIntersect );
Free2IntersectList(pList1, pList2, pIntersect);
pList1 = pList2 = pIntersect = NULL;
}
return 0;
}
{
pDel = pIntersect;
pIntersect = pIntersect->pNext;
free( pDel );
}
return TRUE;
}
int main(void)
{
// Test
{
struct LinkList* pIntersect = NULL;
struct LinkList* pList1 = NULL;
struct LinkList* pList2 = NULL;
Create2IntersectList(&pList1, &pList2);
printList(pList1);
printList(pList2);
pIntersect = GetFirstIntersectNode(pList1, pList2);
printf("\nTest:");
printList( pIntersect );
Free2IntersectList(pList1, pList2, pIntersect);
pList1 = pList2 = pIntersect = NULL;
}
return 0;
}
--------------------编程问答-------------------- 一年左右没玩过程序了,今天无聊进来逛逛.看了半天才搞明白楼主两道题的意思，不过楼主第一题那段程序搞的人焦头烂额。H.next究竟代表的是链表的头结点，还是头结点指向的结点，搞的不是很清楚。另外什么面试官说的从后往前找，不晓得在单向链表中是如何实现的。第二题楼主想法正确，如果单向链表有相同的结点，那么此后的结点都是引用，必然都相同。考官所谓的不知道哪个在相同点之前的结点多，可能是以为两链表重合几个结点后又分离了吧。举例说，设单向链表A有M个结点，单向链表B有N个结点，M>N，他们重合的结点个数为C，必然有C<=N,M-C>N-C的关系.所以说面试官发呆了.
PS:编程业余爱好者在此瞎掰,高手莫拍砖.
我正在使用《Csdn收音机》第一时间获取最新动态！
--------------------编程问答--------------------
学习了~~~
--------------------编程问答--------------------
如果是第一个结点相交，则其后边的结点一定是相同的，否则请问相同的那个结点怎么去指向不同的两个结点呢？
既然你已经肯定了1，就说明你已经理解了我所说的就是一个Y型的链表，2应该也能理解是引用相同了吧：）
--------------------编程问答-------------------- 学习了，顶了 --------------------编程问答-------------------- 如果只是要反转之后的结果的话 使用顺序表显然要优越一点
所以面试官会认为你重新构造一个链表的方法比较笨
而第二题 明显楼主是正确的 不知道面试官怎么想的
如果沿用第一题的想法估计也是转成顺序表倒着找 这两种方法没有多大区别(一个消耗额外的内存一个需要多次遍历) --------------------编程问答-------------------- 收藏 学习算法 --------------------编程问答--------------------
1. 我并不觉得我写的有多花哨，只是用写自己的思路而已。
2. 我同意您所说的需要测试去的，比如，我就没有加入判断链表是否为空，如果加入测试，这个是需要加上的。
3. 关于是否沉下心来听别人的问题，我想这不是听与不听的问题，而是是不是应该听的问题。
--------------------编程问答-------------------- 因为我并不觉得面试官的算法比我的简洁清晰。。。所以才拿来和大家一起讨论。
--------------------编程问答-------------------- 看过了拿分走人 --------------------编程问答-------------------- --------------------编程问答-------------------- 对链表研究不多，回去好好学习一下。。。。 --------------------编程问答-------------------- 学学嘻嘻... --------------------编程问答-------------------- 虽然不懂 链表 支持楼主 --------------------编程问答-------------------- 我都大二完了！要升大三了！课你们写的代码我都还有好多看不懂！！
--------------------编程问答-------------------- --------------------编程问答-------------------- 强人一大把啊 --------------------编程问答-------------------- 不好意思，不知道 --------------------编程问答--------------------
支持LZ。
KISS法则大家都知道，但如何运用，却是各有心得。
楼上一位老兄说得好，“链表长度未知的情况下，用递归不合适”，这才是有实际工程经验的人说的话。如果说“用递归就是逻辑清楚，其它的都是所谓优化的结果”，这恐怕是长期从事课堂教学工作的科班讲师才会有的观点。
--------------------编程问答-------------------- 每个链表的Next节点指针等于当前节点的指针-1就可以了 --------------------编程问答-------------------- 来学习了，链表？回去找找 --------------------编程问答-------------------- 同情楼主
找来的面试官估计只是例行公事，实际要招的人已经内定好了 --------------------编程问答-------------------- 8u08u08u080808 --------------------编程问答-------------------- 学习了……
感谢第一题new 之后会得到一个指针，但是楼主的好像有问题 next应该是node*类型吧 。
后面一个觉得题目说的不清楚 ，返回第一节点是什么意思？返回相同节点的值，还是位置，那个链表里位置。 --------------------编程问答-------------------- 学习了啊 --------------------编程问答-------------------- 参观学习 --------------------编程问答-------------------- --------------------编程问答-------------------- 用栈都是O(n)。
补充：.NET技术 , C#
