### 算法1 二分

#### 参考文献

https://www.acwing.com/solution/LeetCode/content/4487/

#### C++ 代码

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(),m = nums2.size();
if(n > m) {swap(nums1,nums2),swap(n,m);}
int left = 0,right = n,k = (n + m + 1) >> 1;
while(left <= right)
{
int i = (left + right) >> 1,j = k - i;
if(i < n && nums1[i] < nums2[j - 1] )
left = i + 1;
else if(i > 0 && nums1[i - 1] > nums2[j])
right = i - 1;
else
{
int max_left,min_right;
if(i == 0) max_left = nums2[k - 1];
else if(j == 0) max_left = nums1[k - 1];
else max_left = max(nums1[i - 1],nums2[j - 1]);
if((n + m) % 2 == 1) return max_left;

if(i == n) min_right = nums2[j];
else if(j == m) min_right = nums1[i];
else min_right = min(nums1[i],nums2[j]);
return (max_left + min_right)/2.0;
}
}
return 0.0;
}
};


### 算法1延伸

#### 参考文献

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

#### C++ 代码

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(),m = nums2.size();
if(n > m) {swap(nums1,nums2),swap(n,m);}

int left = 0,right = n * 2;
int leftMax1, leftMax2, rightMin1, rightMin2;
int i, j;

while (left <= right) {
i = (left + right) >> 1;
j = m + n -i;

leftMax1 = (i == 0) ? INT_MIN :nums1[(i - 1) /2];
rightMin1 = (i == n * 2) ? INT_MAX : nums1[i /2];
leftMax2 = (j == 0) ? INT_MIN : nums2[(j - 1) / 2];
rightMin2 = (j == m * 2) ? INT_MAX :nums2[ j / 2];

if (leftMax2 > rightMin1)
left = i + 1;
else if (leftMax1 > rightMin2)
right = i - 1;
else
break;
}
return (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2.0;
}
};


### 算法2 分治法

#### 参考文献

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

#### C++ 代码

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size(), len = len1 + len2;
if (len % 2 == 0) {
int left = getKthSmallest(nums1, 0, nums2, 0, len / 2);
int right = getKthSmallest(nums1, 0, nums2, 0, len / 2 + 1);
return (left + right) / 2.0;
}
else
return getKthSmallest(nums1, 0, nums2, 0, len / 2 + 1);
}

int getKthSmallest(vector<int> &nums1, int start1, vector<int> &nums2, int start2, int k) {
if (nums1.size() - start1 > nums2.size() - start2)
return getKthSmallest(nums2, start2, nums1, start1, k);
if (start1 == nums1.size())
return nums2[start2 + k -1];
if (k == 1)
return min(nums1[start1], nums2[start2]);

//缩小范围
int s1 = start1 + min(k / 2, int(nums1.size() - start1));
int s2 = start2 + min(k / 2, int(nums2.size() - start2));
if (nums1[s1 - 1] > nums2[s2 - 1])
return getKthSmallest(nums1, start1, nums2, s2, k - (s2 - start2));
else
return getKthSmallest(nums1, s1, nums2, start2, k - (s1 - start1));
}
};


### 算法2 分治法延伸

#### C++ 代码

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size(), len = len1 + len2;
int left = (len + 1) / 2;
int right = (len + 2) /2;
return (getKthSmallest(nums1, 0, nums2, 0, left) + getKthSmallest(nums1, 0, nums2, 0, right)) / 2.0;
}

int getKthSmallest(vector<int> &nums1, int start1, vector<int> &nums2, int start2, int k) {
if (nums1.size() - start1 > nums2.size() - start2)
return getKthSmallest(nums2, start2, nums1, start1, k);
if (start1 == nums1.size())
return nums2[start2 + k -1];
if (k == 1)
return min(nums1[start1], nums2[start2]);

//缩小范围
int s1 = start1 + min(k / 2, int(nums1.size() - start1));
int s2 = start2 + min(k / 2, int(nums2.size() - start2));
if (nums1[s1 - 1] > nums2[s2 - 1])
return getKthSmallest(nums1, start1, nums2, s2, k - (s2 - start2));
else
return getKthSmallest(nums1, s1, nums2, start2, k - (s1 - start1));
}
};


#### C++ 代码

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//增加一个头结点指针
// 增加一个游标

//标记前后两个要交换的节点
ListNode* first = NULL;
ListNode* second = NULL;

//遍历所有节点
while (cur->next != NULL) {
first = cur->next;
if (first == NULL)
break;
second = first->next;
if (second == NULL)
break;
//交换节点
cur->next = second;
first->next = second->next;
second->next = first;
cur = first;
}