链表逆序问题，求指教 （下一期讨论TLV报文）

zhangtongjian

将一带链表头List head的单向链表逆序。

分析：

  1). 若链表为空或只有一个元素，则直接返回；

  2). 设置两个前后相邻的指针preNode ,pNextNode . 将preNode 所指向的节点作为pNextNode 指向节点的后继；

  3). 重复2),直到pNextNode 为空

  4). 调整链表头和链表尾

  部分实现代码：
  typedef struct tagList
  {
    int data；
    struct tagList *pNext；
   }List_Node;

  List_Node *Head；
(1) 先构造一个带头结点的链表，代码略（我想这个学过C语言的都会）
（2）Deamo：

       List_Node *ReverseList(List_Node * Head)
       {
           List_Node *pTemp = NULL；
           List_Node *preNode = Head->pNext;
           List_Node *pNextNode = Head->pNext->pNext;
           /* 如果链表为空或则只有一个节点，则直接返回 */
           if (NULL == Head->pNext || Head->pNext->Next)
              return Head;
          /* 当循环结束时，此时preNode 指向原始链表最后一个节点*/
           while（NULL != pNext）
           {
              pTemp = pNextNode ->pNext;
              pNextNode ->pNext = preNode ;
              preNode = pNextNode ;
              pNextNode = pTemp ;
           }
         
          /*设置链表尾*/
          Head->pNext->pNext = NULL;
         
          /*设置链表头*/
         Head->pNext = preNode ;
         return Head;
       }

lxyscls

1. List_Node *ReverseList(List_Node * Head)
   
2. {
   
3.     List_Node *r = NULL;
   
4.     List_Node *n, *h = head;
   
5. 
   
6.     while (h) {
   
7.         n = h->next;
   
8.         h->next = r;
   
9.         r = h;
   
10.         h = n;
    
11.     }
    
12.     return r;
    
13. }

复制代码

为什么要带头？链表反转的核心是把链表分为左右两部分...

0n10rz1r0

回复 1# zhangtongjian


    代码不够严谨

cobras

最简单的还是双向循环链表，不管正反，通吃。

zhangtongjian

分成左右俩部分是什么意思？？回复 2# lxyscls


   

zhangtongjian

哪地方不严谨尼  求支出回复 3# 0n10rz1r0


   

zhaohongjian000

回复 6# zhangtongjian

1.             
   
2.            List_Node *pNextNode = Head->pNext->pNext;
   
3.            /* 如果链表为空或则只有一个节点，则直接返回 */
   
4.            if (NULL == Head->pNext || Head->pNext->pNext)
   
5.               return Head;
   

复制代码

如果Head->pNext为NULL，第一行就core dump了。


另外，单链表带空头节点是跟着书上学的。但，也许是我孤陋寡闻，这些年见过的实现都没有空头节点。


（更新：代码里面不能给文字加颜色，真蛋疼）

lxyscls

zhangtongjian 发表于 2014-09-19 21:12
分成左右俩部分是什么意思？？回复 2# lxyscls

当然是已经逆转的部分和未逆转的部分咯

cobras

如果是我，我会这样写：（手机写的，没编译，但算法是对的）
int ReverseLink(List_Node **io_list)
{
    List_Node *list_old,*list_new,*node;

    list_old = *io_list;
    list_new = NULL;

    while (list_old != NULL) {
       node = list_old;
       list_old = list_old-〉pNext;
       node-〉pNext = list_new;
       list_new = node;
    }

    *io_list = list_new;
    return 0;
}