剑指offer之反转链表

1 问题

反转链表，比如0->1->2->3反转后变成了3->2->1->0

2 分析

搞3个指针，初始化一个指针，让头结点指向这里，然后另外一个指针初始化为NULL，然后让第一个节点指向这里，然后头结点依次向右移，这个初始化为NULL的指针也向右移动，然后最后当头结点的next指向NULL的时候，我们直接返回这个节点就行了。

3 代码实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct Node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int val;
     
    
   

    

     

    
    

     
 struct Node *next;
     
    
   

    

     

    
    

     

      } Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

       *print list
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      void print_list(Node *head)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (head == NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("head is NULL\n");
     
    
   

    

     

    
    

     
 return;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Node *p = head;
     
    
   

    

     

    
    

     
 while (p != NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("value is %d\n", p->val);
     
    
   

    

     

    
    

     

       p = p->next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

       *reverse list
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      struct Node* reverse(Node *head)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (head == NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("reverse head is NULL\n");
     
    
   

    

     

    
    

     
 return NULL;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Node *end = NULL;
     
    
   

    

     

    
    

     

       Node *p = head;
     
    
   

    

     

    
    

     

       Node *start = NULL;
     
    
   

    

     

    
    

     
 while (p != NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 //next node
     
    
   

    

     

    
    

     

       Node *next = p->next;
     
    
   

    

     

    
    

     
 //If next is NULL, we will store p, we will return p in the end;
     
    
   

    

     

    
    

     
 if (next == NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       end = p;
     
    
   

    

     

    
    

     

       } 
     
    
   

    

     

    
    

     

       p->next = start;
     
    
   

    

     

    
    

     

       start = p;
     
    
   

    

     

    
    

     

       p = next;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return end;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 //0->1->2->3;
     
    
   

    

     

    
    

     

       Node head, node1, node2, node3;
     
    
   

    

     

    
    

     

       head.val = 0;
     
    
   

    

     

    
    

     

       head.next = &node1;
     
    
   

    

     

    
    

     

       node1.val = 1;
     
    
   

    

     

    
    

     

       node1.next = &node2;
     
    
   

    

     

    
    

     

       node2.val = 2;
     
    
   

    

     

    
    

     

       node2.next = &node3;
     
    
   

    

     

    
    

     

       node3.val = 3;
     
    
   

    

     

    
    

     

       node3.next = NULL;
     
    
   

    

     

    
    

     

       print_list(&head);
     
    
   

    

     

    
    

     
 printf("list will reverse\n");
     
    
   

    

     

    
    

     

       Node *hello = reverse(&head);
     
    
   

    

     

    
    

     

       print_list(hello);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

  

   

    

     

    
    

     

      value is 0
     
    
   

    

     

    
    

     

      value is 1
     
    
   

    

     

    
    

     

      value is 2
     
    
   

    

     

    
    

     

      value is 3
     
    
   

    

     

    
    

     

      list will reverse
     
    
   

    

     

    
    

     

      value is 3
     
    
   

    

     

    
    

     

      value is 2
     
    
   

    

     

    
    

     

      value is 1
     
    
   

    

     

    
    

     

      value is 0
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/89856077