新近在学习算法，跟大家讨论一条题目

最近在学习算法，跟大家讨论一条题目
是微软面试一百题里面的题目，我有一个地方看不懂，希望跟大家讨论一下。

题目：用一种算法颠倒一个连接表的顺序（应该是单链表吧）。要求不要递归做。

下面是答案的代码，有点看不懂

Node * revereNonrecurisve(Node * head)
{
if (head == null)
{
return head;
}

Node * p = head;
Node * previous = null;
while (p->next != null)
{
p->next = previous;
previous = p;
p = p->next;
}
p->next = previous;
return p;
}

在第一次while循环中，p->next不是应该就被赋值为null了么？第二次就跳出循环了，难道是我语言功底太差，看不懂这个while循环么？
谁能给我解释一下?
[解决办法]
自己模拟几次while循环就可以了
while循环中的三句，相当于每次从原链表摘取第一个节点，添加到新链表的头部。
循环结束的时候，把原链表最后1个节点（next指针是NULL）接到新链表头部。

[解决办法]
假设有三个节点，p、q、r。q = p->next; r = q->next.
第一次循环置p->next = null;  previous = p; 并取得p的下一个节点，也即q。
第二次循环置q->next = previous(在第一次循环中previous = p;)，previous = q;此时q->next = p;并取得q的下一个节点，也即r。
第三次循环置r->next = previous(在第二次循环中previous = q;),previous = r;此时r->next = q;并取得r的下一个节点，也即为null。循环结束
从第三次依次往后看，r->next = q; q->next = p; p->next = null;完成了链表的逆转

[解决办法]
循环体中的这三句：

        p->next = previous;
        previous = p;
        p = p->next;

是不是顺序有问题啊？
我感觉应该是这么写的：

        
        previous = p;
        p = p->next;
        p->next = previous;

------解决方案--------------------

貌似还是不行，不管怎样都会丢掉p->next，还是看2楼的。
[解决办法]

Node * revereNonrecurisve(Node * head)
{
    if (head == null)
    {
        return head;
    }
 
    Node * p = head;
    Node * previous = null;
    while (head != null)
    {
        head = p->next;
        p->next = previous;
        previous = p;
        p = head;
    }
    p->next = previous;
    return p;
}

[解决办法]
做了个很简单的能运行的demo来测试反转链表的函数。
包括 建立链表（类似栈，每次加在头部，逆序的），显示链表所有内容，反转链表，删除链表。

#include <iostream>
 
struct Node
{
int data;
Node* next;
};

void addtolist(Node*& head, int a)
{
Node* p = new Node;
p->data = a;
p->next = head;
head = p;
}

void showlist(Node* head)
{
while (head != NULL)
{
std::cout << head->data << ' ';
head = head->next;
}
std::cout << std::endl;
}

void eraselist(Node*& head)
{
while (head != NULL)
{
Node* p = head;
head = head->next;
delete p;
}
}


Node * revereNonrecurisve(Node * head)
{
Node * previous = NULL;
Node* p = NULL;
while (head != NULL)
{
p = head->next;
head->next = previous;
previous = head;
head = p;
}
return previous;
}

int main()
{
Node* head = NULL;
for (int i = 0; i < 10; i++)
addtolist(head, i + 1);
showlist(head);
head = revereNonrecurisve(head);
showlist(head);
eraselist(head);
return 0;
}

// 运行结果 
 
// 10 9 8 7 6 5 4 3 2 1
// 1 2 3 4 5 6 7 8 9 10

查看更多 下一篇