【C/C++练习题】反转链表

《剑指Offer》面试题24：反转链表

1 题目

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

2 分析

改变节点的指向，引用改节点需要两个指针，一个用于指向当前指针p1，另一个用来指向它的上一个节点。另外，为了防止操作过程中链表（p1节点与其下一个节点）断开而丢失，要一个指针p3来保存下一个节点。一共需要3个指针操作。

3 代码

  

   

    

     

    
    

     

      #include "iostream"
     
    
   

    

     

    
    

     

      #include "cstdlib"
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //问题：翻转链表
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m_nValue;
     
    
   

    

     

    
    

     

      	node* m_pNext;
     
    
   

    

     

    
    

     

      }ListNode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Print_list_node(ListNode* pHead);
     
    
   

    

     

    
    

     

      ListNode* Reverse_list(ListNode* pHead);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void test01()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	ListNode* pHead  = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode1 = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode2 = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode3 = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          pHead = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode1 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode2 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode3 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	if (pHead == NULL || pNode1 == NULL || pNode2 == NULL || pNode3 == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		cout << "malloc fail" << endl;
     
    
   

    

     

    
    

     
		return ;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pHead->m_nValue = 0;
     
    
   

    

     

    
    

     

      	pHead->m_pNext  = pNode1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode1->m_nValue = 1;
     
    
   

    

     

    
    

     

      	pNode1->m_pNext  = pNode2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode2->m_nValue = 2;
     
    
   

    

     

    
    

     

      	pNode2->m_pNext  = pNode3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode3->m_nValue = 3;
     
    
   

    

     

    
    

     

      	pNode3->m_pNext  = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       	cout << "current list:";
     
    
   

    

     

    
    

     
 	Print_list_node(pHead);		//打印链表节点信息
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       	pHead = Reverse_list(pHead);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       	cout << "reverse list:";
     
    
   

    

     

    
    

     
 	Print_list_node(pHead);		//反转后
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	test01();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：反转链表
     
    
   

    

     

    
    

     

      //输入：pHead链表头节点指针
     
    
   

    

     

    
    

     

      //返回：反转后的链表首节点指针
     
    
   

    

     

    
    

     

      ListNode* Reverse_list(ListNode* pHead)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.判断参数的有效性
     
    
   

    

     

    
    

     
	if (pHead == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return NULL;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	ListNode* Reverse_pHead = NULL;		//反转后的头节点指针
     
    
   

    

     

    
    

     

      	ListNode* pNode = pHead;	//当前节点指针
     
    
   

    

     

    
    

     

      	ListNode* pPrev = NULL;		//前一个节点指针
     
    
   

    

     

    
    

     
	while (pNode != NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		//1.保存后一个节点
     
    
   

    

     

    
    

     

      		ListNode* pNext = pNode->m_pNext;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		//2.尾节点-->头节点
     
    
   

    

     

    
    

     
		if (pNext == NULL)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			Reverse_pHead = pNode;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		//3.改变当前节点指针的指向
     
    
   

    

     

    
    

     

      		pNode->m_pNext = pPrev;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		//4.偏移指针 pPrev pNode
     
    
   

    

     

    
    

     

      		pPrev = pNode;
     
    
   

    

     

    
    

     

      		pNode = pNext;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return Reverse_pHead;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：打印链表所有节点
     
    
   

    

     

    
    

     

      //输入：pHead 头节点地址
     
    
   

    

     

    
    

     

      //返回：无
     
    
   

    

     

    
    

     

      void Print_list_node(ListNode* pHead)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (pHead != NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		while (pHead->m_pNext != NULL)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			cout << pHead->m_nValue << ",";	//打印节点信息
     
    
   

    

     

    
    

     

      			pHead = pHead->m_pNext;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		cout << pHead->m_nValue << endl;	//打印尾节点
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

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

原文链接：blog.csdn.net/feit2417/article/details/98758388