剑指offer（15）——C++实现反转单向链表

柔光的暖阳◎ 2024-04-17 05:27 13阅读 0赞

# 题目 #

输入一个链表，反转链表后，输出新链表的表头。

# 考察点 #

*  链表、指针的编程能力
 *  思维的全面性和代码的鲁棒性

# 解题思路 #

避免链表断开后找不到后继节点，所以需要事先保存后继节点信息。  
设置三个指针，分别表示前继、当前、后继

# 完整代码 #

/*15-反转链表输出新链表头结点*/
    #include<iostream>
    using namespace std;
    
    struct ListNode {
        
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
        
    	}
    };
    class Solution {
        
    public:
    	//非递归方式
    	ListNode* ReverseList(ListNode* pHead) 
    	{
        
    		ListNode *rever = NULL;
    		ListNode *pNode = pHead;
    		ListNode *pPrev = NULL;
    		while (pNode != NULL)
    		{
        
    			ListNode *pNext = pNode->next;//保存反转前的后继节点 1(prev)->2(node)->3(next)->4
    			if (pNext == NULL)//只有一个节点
    				rever = pNode;
    			//反转
    			pNode->next = pPrev;//此时pNode指向prev 1(prev)<-2(node) 3(next)->4
    			pPrev = pNode;//prev node next均向后移一位，1<-2(prev) 3(node)->4(next)
    			pNode = pNext;//根据前面保存好的next节点就可以轻易找到断开后的下一个节点 即节点3 1<-2(prev) 3(node)->4(next)
    		}
    		return rever;
    	}
    	//递归方式
    	ListNode* ReverseList2(ListNode* pHead)
    	{
        
    		if (pHead == NULL || pHead->next == NULL)
    			return pHead;
    		ListNode *rever = ReverseList2(pHead->next);
    		pHead->next->next = pHead;
    		pHead->next = NULL;
    		return rever;
    	}
    };
    int main()
    {
        
    	ListNode *p1 = new ListNode(5); ListNode *p2 = new ListNode(4); ListNode *p3 = new ListNode(3);
    	ListNode *p4 = new ListNode(2); ListNode *p5 = new ListNode(1);
    	p1->next = p2; p2->next = p3; p3->next = p4; p4->next = p5;
    	Solution s;
    	ListNode* result;
    	//result = s.ReverseList(p1);
    	result = s.ReverseList2(p1);
    	cout << result->val << endl;
    	return 0;
    }

# 编程问题 #

*  循环选择，当不知道表长时，无法获取确定 循环次数时使用while。