题目&＃xff1a;
输入一个链表&＃xff0c;反转链表后&＃xff0c;输出链表的所有元素。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
}
};
思路&＃xff1a;使用辅助节点把链表掉头
class Solution {
public:ListNode* ReverseList(ListNode* pHead) { if(pHead&＃61;&＃61;NULL) return NULL;//注意程序鲁棒性 ListNode* pNode&＃61;pHead;//当前指针ListNode* pReverseHead&＃61;NULL;//新链表的头指针ListNode* pPrev&＃61;NULL;//当前指针的前一个结点 while(pNode!&＃61;NULL){//当前结点不为空时才执行ListNode* pNext&＃61;pNode->next;//链断开之前一定要保存断开位置后边的结点if(pNext&＃61;&＃61;NULL)//当pNext为空时&＃xff0c;说明当前结点为尾节点pReverseHead&＃61;pNode;pNode->next&＃61;pPrev;//指针反转pPrev&＃61;pNode;pNode&＃61;pNext;}return pReverseHead;}
}思路二&＃xff1a;递归
class Solution {
public:ListNode* ReverseList(ListNode* pHead) {//如果链表为空或者链表中只有一个元素if(pHead&＃61;&＃61;NULL||pHead->next&＃61;&＃61;NULL) return pHead; //先反转后面的链表&＃xff0c;走到链表的末端结点ListNode* pReverseNode&＃61;ReverseList(pHead->next); //再将当前节点设置为后面节点的后续节点pHead->next->next&＃61;pHead;pHead->next&＃61;NULL;return pReverseNode; }
};
京公网安备 11010802041100号