[动态规划][链表]不同路径Ⅱ、反转链表
题目：
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
问总共有多少条不同的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
题解：该题目标注为中等难度，有点言过其实。
典型动态规划的题，其状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]
class Solution {public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,1));for(int i=1;i<m;++i){for(int j=1;j<n;++j){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}};
题目二：
翻转链表
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
题解：该题重点在于要注意边界条件，同时要注意题目要求是一次遍历完成，做完该题，我发现其他很多人的做法虽然也做出来但是不符合题目要求。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {public://链表分为三种情况// a-->b-->c-->d-->e-->f-->null//假设 --- ---// | |// \|/ \|/// m n//边界情况一// a-->b-->c-->d-->e-->f-->null// --- ---// | |// \|/ \|/// m n//边界情况二// a-->b-->c-->d-->e-->f-->null// --- ---// | |// \|/ \|/// m nListNode* reverseBetween(ListNode* head, int m, int n) {if(m==n) return head;ListNode* node=head;ListNode* subnode=head;ListNode* pre=nullptr;ListNode* curr=nullptr;ListNode* next=nullptr;ListNode* Flag;int num=0;//引入（num+1>n）条件，确保翻转结束节点为最后节点时，更新返回值while(node!=nullptr||num+1>n){++num;if(num<m){//记录开始反转的上一个节点，以便连接翻转部分链表if(num+1==m){subnode=node;}node=node->next;continue;}//判断是否完成反转部分if(num>n){//开始翻转部分需要直接链接上后续未翻转部分Flag->next=node;if(m!=1){ //如果是从收个节点反转，则头结点调整subnode->next=pre;}else{//如果从第一个节点开始翻转，其首节点改变head=pre;}break;}curr=node;next=node->next;node->next=pre;pre=curr;node=next;//此处记录开始翻转的节点if(num==m){Flag=pre;}}return head;}};