和面试官对两道数据结构算法题持不同意见，望各位前辈给予指教，在此多谢各位了！

Question

本帖最后由 whywherewhen 于 2010-08-14 03:55:07 编辑

Answer 1

先不说算法，感觉你这个代码定义有点问题
1、q定义时无需new
2、各变量定义类型应该是链表类型LinkList，而不是Node
面试官的方法：
从链表的开始循环到结束，然后从最后一个结点开始往前依次交换结点。
================
单向链表，怎么往前依次呢？把这个解决了算法就简单了

Answer 2

要是C++用指针，这算法就简单了
每个链表的Next节点指针-1就可以了

Answer 3

每个链表的Next节点指针等于当前节点的指针-1就可以了

Answer 4

Next节点-1？链表又不是顺序表，-1能找到前一个元素？

Answer 5

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），我没看出面试官的算法比你的好在哪，不过人家既然是面试官，你又想某的这个职位当时最好是按人家的思路来，呵呵，其他可以以后再说嘛！

Answer 6

这种不懂装懂，或说懂一点装全懂，固执听不进别人的方法的技术人员，是很难一起共事的。
LZ还是不要去了，单向链表能从后往回找么？是不是还得用栈呀！另外LZ应该反问一句，两个链表如果其中一个有环怎么办？还不得死循环了！

Answer 7

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;
}
另外，楼主代码运行结果是错误的。

Answer 8

比较笨的方法用List数组，不过貌似这个有点违背链表算法
 public void ReversLinkList(LinkList H)
        {
            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里的各元素就是反转后的节点
        }

Answer 9

我算法太菜了。所以对这种简单的也想试试。楼主的算法的确不错。不过调用方法不同。反正没测试出正确结果。就按想法，继续写的正确的，规范下命名。方便阅读。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();
    }
}

Answer 10

链表反转
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 的位置（因为多出来的结点肯定不是相同结点），然后再去循环比较。”得出没有。

Answer 11

Peter同志，我估计面试第二题的原意应该指的不是值相同，而是同一个引用，也就是说是那种Y型的链表。这样的话LZ答的就没问题了。

Answer 12

相同的结点,应该是值和Next都相同吧,如果单纯的比较值的话,那肯定两个方法都不对如果是比值和Next的话,由"link2 3 4"可推出,3后面肯定有4,"link1 2 3"肯定是"link1,2,3,4"

Answer 13

我试了下,楼主第一题的方法正确,
    class Program
    {
        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;
            }        }

Answer 14

他写的next。你的是Head。没说思路不对。你直接用他的不改试试？

Answer 15

以他的代码,应该H.Next是链表的头可能是这样定义的:
class LinkList
        {
            public Node Next = null;
        }否则,肯定是  class LinkList:Node {};
如果是第二种的话,它应该传入LinkList* H,否则无法修改H本身

Answer 16

其实这个方法最大的问题，除了要跑两遍之外，其空间复杂度是O(n)的，而反转链表的标准方法空间是O(1)的！

Answer 17

楼主你觉得你的思路确实有问题，关于单向linkedlist反转，我也没看懂你的代码。
要是我，我会这样做：
依次循环第一个链表，将每个结点插入到第二个列表第0个位置（表头），完成之后，看第二个链表，不是反转了？
linkedlist就是在头或中间插入结点很方便，性能也没啥损失。求两个单链表是否有相同结点？如果有相同结点，返回第一个结点
暂时觉得只能做一个m*n的双层循环了，暂时没想到啥好办法。

Answer 18

我也觉得lz至少写的含糊，面试官 又不会像 jointan 一样来迁就你，为你着想。

Answer 19

先不说算法，感觉你这个代码定义有点问题
1、q定义时无需new
2、各变量定义类型应该是链表类型LinkList，而不是Node
面试官的方法：
从链表的开始循环到结束，然后从最后一个结点开始往前依次交换结点。
================
单向链表，怎么往前依次呢？把这个解决了算法就简单了

Answer 20

你这不对吧  LZ都说了引用也相同 那必然是一个Y型  LZ的思路很正确啊