| Mi Manchi = yuan = Whatever is worth doing at all is worth doing well

# 剑指 Offer 18. 删除链表的节点

1692843069339

	struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
	};



	class Solution {
	public:
	ListNode* deleteNode(ListNode* head, int val) {
	if (head == NULL)
	return NULL;

	ListNode* newRoot = new ListNode(0);
	newRoot->next = head;

	ListNode* p1 = newRoot, *p2 = head;

	while (p2 != NULL) {
	if (p2->val == val) {
	p1->next = p2->next;
	break;
	}
	else {
	p1 = p2;
	p2 = p2->next;
	}
	}
	return newRoot->next;

	}
	};

上面的算法使用了头结点法，new 出一个新的头结点，将原先的头结点当做普通结点处理。

1692843383140

1692843396844

1692850592291

	class Solution {
	public:
	vector<int> exchange(vector<int>& nums) {
	int i = 0, j = nums.size() - 1;

	while (i < j) {

	// 找到第一个偶数
	while (nums[i] % 2 == 1 && i < j)
	i++;

	// 找到第一个奇数
	while (nums[j] % 2 == 0 && i < j)
	j--;

	swap(nums[i], nums[j]);
	}

	return nums;
	}
	};

1692844420893

	class Solution {
	public:
	vector<int> exchange(vector<int>& nums)
	{
	int i = 0, j = nums.size() - 1;
	while (i < j)
	{
	while(i < j && (nums[i] & 1) == 1) i++;
	while(i < j && (nums[j] & 1) == 0) j--;
	swap(nums[i], nums[j]);
	}
	return nums;
	}
	};

1692844903365

	class Solution {
	public:
	ListNode* getKthFromEnd(ListNode* head, int k) {
	map<int, ListNode*> mp;

	int i = 1;
	ListNode* ptr = head;

	while (ptr != NULL) {
	mp[i++] = ptr;
	ptr = ptr->next;
	}

	return mp[i - 1 - k + 1];
	}
	};

1692845966506

1692845990473

上图中，下面那个越界的代码是错误的，假如 k = 链表长度，那么第一个循环中 former 也会变成 null。

	class Solution {
	public:
	ListNode* getKthFromEnd(ListNode* head, int k) {
	ListNode former = head, latter = head;
	for(int i = 0; i < k; i++)
	former = former->next;
	while(former != nullptr) {
	former = former->next;
	latter = latter->next;
	}
	return latter;
	}
	};

1692847867544

1692847843048

1692847858650

1692850954796

1692851148072

	class Solution {
	public:
	vector<int> twoSum(vector<int>& nums, int target) {
	int i = 0, j = nums.size() - 1;
	while(i < j) {
	int s = nums[i] + nums[j];
	if(s < target) i++;
	else if(s > target) j--;
	else return { nums[i], nums[j] };
	}
	return {};
	}
	};

	class Solution {
	public:
	string reverseWords(string s) {
	istringstream str(s);
	vector<string> ve;
	string temp;

	while (str >> temp) {
	ve.push_back(temp);
	}
	string res;
	for (int i = ve.size() - 1; i >= 0; i--) {
	if (i)
	res.append(ve[i] + " ");
	else
	res.append(ve[i]);
	}
	return res;
	}
	};

1692853277376

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/

	class Solution {
	public:
	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
	ListNode* pa = headA, * pb = headB;
	int flaga = 1, flagb = 1;

	while (1) {
	if (pa != nullptr && pa == pb) {
	return pa;
	}

	if (pa == nullptr && flaga) {
	pa = headB;
	flaga = 0;
	}
	else if (pa == nullptr && flaga == 0) {
	return NULL;
	}
	else {
	pa = pa->next;
	}

	if (pb == nullptr && flagb) {
	pb = headA;
	flagb = 0;
	}
	else if (pb == nullptr && flagb == 0) {
	return NULL;
	}
	else {
	pb = pb->next;
	}

	}
	}
	};

1692853586973

遍历结点的数量应该加上一个 nullptr

	class Solution {
	public:
	ListNode getIntersectionNode(ListNode headA, ListNode *headB) {
	ListNode A = headA, B = headB;
	while (A != B) {
	A = A != nullptr ? A->next : headB;
	B = B != nullptr ? B->next : headA;
	}
	return A;
	}
	};