从尾到头打印链表 ，合并两个排序的链表、反转链表 ：迭代法

 

目录

 

合并两个排序的链表：

关于迭代法的理解： 

每一层函数功能:

迭代的两个问题：

往里走时：

出来时：

 从尾到头打印链表 返回数组；

每一层函数功能:

迭代的两个问题：

往里走时：

出来时：

反转链表 

每一层函数功能:

迭代的两个问题：

往里走时：

出来时：

---

合并两个排序的链表：

关于迭代法的理解： 

每一层函数功能:

两个结点比较，返回较小结点

迭代的两个问题：

往里走时：

        下一步的递归区间：因为是从小到大排序，所以当p1<= p2时，下一步应该比较p1->next和p2;

出来时：

        返回值是什么：最后出来时，最后一层肯定是直接返回的头节点，每一层也应该返回头结点，从小到达排序，因此当p1<= p2时，返回较小的头节点p1；

        怎么处理：因为是从小到大，当p1<= p2时，因此出来时的头链接是p1->next = 返回值;

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //终止条件；
		if(!pHead1) return pHead2;
		if(!pHead2) return pHead1;
		//
		//函数功能:两个结点比较，返回较小结点
		//开始迭代的两个问题：
		//往里走时：下一步的递归区间：因为是从小到大排序，所以当p1<= p2时，下一步比较p1->next和p2;
		//出来时：返回值是什么，怎么处理；最后出来时，最后一层肯定是直接返回的头节点，因为是从小到大，因此出来时首先建立连接p1->p2;
		if(pHead1->val <= pHead2->val){
			pHead1->next = Merge(pHead1->next, pHead2);
			return pHead1;
		}else{
			pHead2->next = Merge(pHead1, pHead2->next);
			return pHead2;
		}
    }
};

 从尾到头打印链表 返回数组；

每一层函数功能:

先走到底，返回时将结点值放入容器；

迭代的两个问题：

往里走时：

        终止条件：head = NULL；

出来时：

        返回值是什么：使用& ，因此不需要返回值；

        怎么处理：将结点值依次放入vector容器中；

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
  public:
  //这里使用&来传递，
   void reverseList(ListNode* head, vector<int>& v) {
        if(head != NULL){
            reverseList(head->next, v);
            v.push_back(head->val);
        }
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> v;
        reverseList(head, v);
        return v;
    }
};

反转链表 

每一层函数功能:

先走到底，返回时将结点值放入容器；

迭代的两个问题：

往里走时：

        终止条件：最后一个结点；即head.next = NULL；

出来时：

        返回值是什么：最后一个结点，存着当头节点；

        怎么处理：反转指向，之后p指针会自动往左跳；

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* ReverseList(ListNode* pHead) {
		//终止条件；
        if (pHead == NULL || pHead->next == NULL)
            return pHead;
		//
        ListNode* ret = ReverseList(pHead->next);
		
        pHead->next->next = pHead;
        pHead->next = NULL;
        return ret;
    }
};