首页 > 代码库 > 链表类题目总结

链表类题目总结

1、反转链表递归和迭代版本

原题:leetcode 206. Reverse Linked List 

           Reverse a singly linked list.

迭代版本:

  思路:通过举例分析可以知道,在反转其中一个链表后,会发生断裂情况,没法知道下一个链节点,需要建立三个节点,所以需要首先保存后一个节点,然后将后一个结点的next指向前一个节点,接下来依次后退,pPre=pCur;pCur=pNext。

技术分享

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
 
//迭代版本iterator
ListNode* reverseList1(ListNode* head) {
	 if (head == nullptr)
		 return head;
	 ListNode* pNext(0), *pCur = head, *pPre(0), *pRevHead(0);
	 while (pCur != nullptr) {
		 pNext = pCur->next;//首先保存下一结点值
		 if (pNext == nullptr)
			 pRevHead = pCur;

		 pCur->next = pPre;//调整指针

		 pPre = pCur;//结点后移
		 pCur = pNext;

	 }
	 return pRevHead;
  }     
    
};

 递归版本:思路和迭代差不多,只不过在最后两个节点交换的时候,使用递归版本实现。递归要考虑到原函数初始定义会在后面递归的时候不断的重新定义,这里思考出现卡顿,所以引入一个辅助函数。

 ListNode* helper(ListNode* pPre, ListNode* pCur) {
	 ListNode* pNext(0), * pRevHead(0);	
	 if (pCur == nullptr)
		 return pPre;
	 pNext = pCur->next;//首先保存下一结点值
	 if (pNext == nullptr)
		 pRevHead = pCur;
	 pCur->next = pPre;//调整指针
	 return  helper(pCur, pNext);
 }

 ListNode* reverseListRecur(ListNode* head) {	 
	 ListNode *pCur = head, *pPre(0), *pRevHead(0);
	
	 if (head == nullptr) {
		 return head;
	 }
	
	 pRevHead= helper(pPre, pCur);
	 return pRevHead;
 }

  

 

链表类题目总结