Tag Archives: 快慢指针

LeetCode Reorder List

LeetCode Reorder List
Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.


本题要求把单链表重新排序,规则是第一个节点接最后一个节点,第二个节点接倒数第二个节点,以此类推。要求in-place,不能借助额外的空间。
这个题我一开始想到的是递归解法,就是首先把L0和Ln接好,然后递归的在L1->...->L(n-1)重排序。但是这样的算法性能肯定很差,因为首先要找到尾节点就很麻烦,还要递归的找尾节点。
看了网上的题解,发现真是巧妙。把链表重排序之后的结果其实相当于先把链表从中点分成前后两段,然后把后半段链表逆序,最后合并两个链表,合并的时候交替从两个链表中取节点拼接起来。
举个例子,0->1->2->3->4,中点是2,分成两段之后就是0->1和2->3->4,然后把第二个链表逆序为4->3->2,最后交替拼接这两个链表,结果就是0->4->1->3->2。、
所以知道思路之后就好办了,找中点可以用快慢指针法,链表逆序用头插法,最后拼接也不是什么难事,不过整合起来代码稍微有点长。
完整代码如下:

class Solution {
public:
	void reorderList(ListNode* head) {
		if (head == NULL || head->next == NULL || head->next->next == NULL)return;
		// find mid node
		ListNode *slow = head, *fast = head, *pre = slow;
		while (slow->next != NULL&&fast != NULL&&fast->next != NULL) {
			pre = slow;
			slow = slow->next;
			fast = fast->next->next;
		}
		pre->next = NULL;
		// reverse [mid,end]
		ListNode *par = new ListNode(0), *tail;
		while (slow) {
			tail = slow->next;
			slow->next = par->next;
			par->next = slow;
			slow = tail;
		}
		//merge 2 list
		par = par->next;
		ListNode *new_head = new ListNode(0), *h = new_head;
		while (head || par) {
			if (head == NULL) {
				h->next = par;
				par = par->next;
			}
			else {
				h->next = head;
				head = head->next;
				h = h->next;
				h->next = par;
				par = par->next;
			}
			h = h->next;
		}
		head = new_head->next;
	}
};

本代码提交AC,用时59MS。

LeetCode Odd Even Linked List

LeetCode Odd Even Linked List
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...


链表题,要求把链表中的奇数位节点连接起来,偶数位节点也连接起来,最后这两个链表连接起来。要求O(1)的空间复杂度和O(n)的时间复杂度。
因为奇数链表和偶数链表都是从原链表中隔一个取一个,立马联想到快慢指针,在这个题里,我们设置两个快指针fast1和fast2,分别指向奇数节点和偶数节点,然后分别取下来,接到odd和even链表中。最后把odd的tail指向even的head就搞定了。符合O(1)空间复杂度和O(n)时间复杂度。
完整代码如下:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
		if (head == NULL)return head;
		ListNode *odd = new ListNode(0), *even = new ListNode(0);
		ListNode *otail = odd, *etail = even;
		ListNode *fast1 = head, *fast2 = head->next;
		while (fast1 || fast2) {
			otail->next = fast1;
			etail->next = fast2;
			if (otail)otail = otail->next;
			if (etail)etail = etail->next;
			if (fast2)fast1 = fast2->next;
			else fast1 = NULL;
			if (fast1)fast2 = fast1->next;
			else fast2 = NULL;
		}
		otail->next = even->next;
		return odd->next;
    }
};

本代码提交AC,用时16MS。
二刷。其实不用快慢指针,直接根据奇偶性就可以了,更简洁的代码如下:

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode *odd = new ListNode(0), *even = new ListNode(0);
        int cnt = 1;
        ListNode *cur = head, *otail = odd, *etail = even;
        while(cur) {
            if(cnt & 1) {
                otail->next = cur;
                otail = otail->next;
            }
            else {
                etail->next  =cur;
                etail = etail->next;
            }
            cur = cur->next;
            ++cnt;
        }
        otail->next = even->next;
        etail->next = NULL; // caution!!!
        return odd->next;
    }
};

本代码提交AC,用时19MS。

LeetCode Find the Duplicate Number

LeetCode Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

一个长度为n+1的数组,包含1~n的数字,证明至少有一个数字重复,并找出这个重复数字。
证明好说,鸽巢原理。要求在线性时间复杂度和常数空间复杂度把这个重复的数字找出来就有难度了,而且不能修改原数组,难以用上LeetCode Find All Numbers Disappeared in an Array的技巧。
这题确实hard,看了看提示,以及网上的题解,现总结如下。
第一种解法是二分搜索。根据鸽巢原理,如果有n+1个[1,n]的数,则必有一个数重复了,把区间分成[1,m]和[m+1,n],则重复的数字要么出现在[1,m],要么出现在[m+1,n],所以只需统计一下小于等于和大于m的数字的个数,数字多的那个区间肯定是存在重复数字的区间。然后在那个区间递归的找下去,直到找到重复数字。
完整代码如下:

class Solution {
public:
	int findDuplicate(vector<int>& nums) {
		int low = 1, high = nums.size() - 1;
		while (low < high) {
			int mid = (low + high) / 2, low_cnt = 0;
			for (int i = 0; i < nums.size(); ++i) {
				if (nums[i] <= mid)++low_cnt;
			}
			if (low_cnt > mid) {
				high = mid;
			}
			else {
				low = mid + 1;
			}
		}
		return low;
	}
};

本代码提交AC,用时9MS。
还有一种解法和LeetCode Linked List Cycle II很类似,如果存在重复数字,则使用下标递归访问的时候,会出现循环访问。首先通过快慢指针找到循环相遇点,然后慢指针回到原点,快慢指针按相同速度前进,直到遇到函数值相同时停止,这个相同的函数值即为重复数字。一些证明可以参考这个博客
完整代码如下:

class Solution {
public:
	int findDuplicate(vector<int>& nums) {
		int slow = 0, fast = 0;
		while (true) {
			slow = nums[slow];
			fast = nums[nums[fast]];
			if (slow == fast)break;
		}
		slow = 0;
		while (true) {
			slow = nums[slow];
			fast = nums[fast];
			if (slow == fast)return slow;
		}
	}
};

本代码提交AC,用时13MS。

LeetCode Linked List Cycle II

LeetCode Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?


本题在LeetCode Linked List Cycle的基础上更进一步,需要求出链表中环的起点位置。
接上一题,相遇位置在Z,此时如果令slower=head,然后slower和faster都以相同的速度走a步,则slower刚好能到环的起点位置Y,那么faster会在哪里呢。
上一题推出来相遇的时候有:a+b=(n-2m)c,如果faster在相遇点走a步,则相当于走了a=(n-2m)c-b,(n-2m)c相当于绕圈n-2m次,(n-2m)c-b的意思就是在z点绕圈n-2m次的基础上,退回b步,看图,退回b步正好到达了环的起点Y。
所以快慢指针再走a步之后,正好在环的起点相遇了!
于是本题的思路就是:先用上一题的方法找到相遇位置,然后slower回到head节点,slower和faster都再次单步走,再次相遇时,就是环的起点。
完整代码如下:

class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		if (head == NULL || head->next == NULL)return NULL;
		ListNode *faster = head, *slower = head;
		while (faster->next != NULL&&faster->next->next != NULL) {
			faster = faster->next->next;
			slower = slower->next;
			if (faster == slower)break;
		}
		if (faster->next == NULL || faster->next->next == NULL)return NULL;
		slower = head;
		while (slower != faster) {
			slower = slower->next;
			faster = faster->next;
		}
		return slower;
	}
};

本代码提交AC,用时13MS。

LeetCode Linked List Cycle

LeetCode Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?


本题要判断一个链表中是否包含环,注意这里的环可能是局部的环,并不一定是链表头尾相连那种环,比如下图。

解题思路是使用快慢指针,如果链表中有环,则快慢指针一定会在某处相遇,证明请看这篇博客,我试着重述一遍:
首先请看示意图,假设链表起点为X,环的起点为Y,环的总长度为c,快慢指针在环的Z点相遇,YZ=b,XY=a。则有
a+b+mc=s---(1)
a+b+nc=2s----(2)
(1)和(2)式分别为慢快指针的等式,其中s表示满指针走过的节点,则快指针走过两倍的s,m和n分别为慢快指针绕圈的圈数,显然n>m。
把(1)代入(2)得到a+b=(n-2m)c。假设真的存在环,则a和c是链表的固有值,是已知量,所以如果能找到m,n,b的一组解,则说明假设成立,真的存在环。
令m=0,n=a,b=ac-a,则这一组解是满足上面的方程(1)和(2)的,也满足n>m。因为环的长度>1,所以b也是大于0的。既然找到一组解,说明假设成立,即存在环。也就是说,我们可以用这种方法判断环是否存在。

完整代码如下:

class Solution {
public:
	bool hasCycle(ListNode *head) {
		if (head == NULL || head->next == NULL)return false;
		ListNode *faster = head, *slower = head;
		while (faster->next != NULL&&faster->next->next != NULL) {
			faster = faster->next->next;
			slower = slower->next;
			if (faster == slower)return true;
		}
		return false;
	}
};

本代码提交AC,用时9MS。
证明参考:
https://stackoverflow.com/a/6110767/2468587
https://math.stackexchange.com/a/913529/161019

LeetCode Palindrome Linked List

LeetCode Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?


本题要判断一个单向链表是否为回文链表。之前LeetCode Valid Palindrome判断的是数组,可以直接访问数组的头尾元素,但是链表不可以随机访问。
仔细观察一下,下面两条回文链表:

  1. 1->2->3->4->5->4->3->2->1
  2. 1->2->3->4->4->3->2->1

判断回文链表最原始的方法是从左往右读一遍和从右往左读一遍,如果读得的结果一样就是回文,比如第1条回文,从左往右是123454321,从右往左也是123454321,所以它是回文。
但是其实我们可以不用完整读一遍,我们只读一半就可以了,比如回文1的前半部分是1234,后半部分是4321,前半部分顺着读和后半部分倒着读都是1234,这样就足以说明是回文串了。
紧接着,对于链表,我们就有这样一种解题思路:首先找到链表的中间节点,然后把后半部分链表逆序,最后看看逆序的后半部分和顺序的前半部分是否相同。
找链表的中间节点的常规思路就是快慢指针,这个在很多题中都用到了,需要指出的是,回文链表有两种情况,一种是形如1的奇数个元素,另一种是形如2的偶数个元素。如果用快慢指针找中点,1能找到真正的中点5,2能找到前一个中点4,所以我们判断回文的时候,只需要把中点后面的链表逆序,然后只比较后半部分的链表元素。比如1的情况,逆序后半部分之后得到1->2->3->4,那么前半部分也只需要比较1->2->3->4,不需要比较5,因为这是奇数链表的中点,前后链表共享的元素;2的情况,逆序后半部分之后得到1->2->3->4,前半部分也是1->2->3->4,偶数长度的情况就会把中间的两个元素分到前后两部分。
完整代码如下:

class Solution {
public:
	bool isPalindrome(ListNode* head) {
		if (head == NULL || head->next == NULL)return true;
		ListNode *faster = head, *slower = head;
		while (faster->next != NULL&&faster->next->next != NULL) {
			faster = faster->next->next;
			slower = slower->next;
		}
		//bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
		ListNode *head2 = slower, *prior = slower->next, *tail;
		head2->next = NULL;
		while (prior != NULL) { // 逆序后半段链表
			tail = prior->next;
			prior->next = head2->next;
			head2->next = prior;
			prior = tail;
		}
		head2 = head2->next;
		while (head2 != NULL) {
			if (head->val != head2->val)return false;
			head = head->next;
			head2 = head2->next;
		}
		return true;
	}
};

本代码提交AC,用时25MS。

LeetCode Convert Sorted List to Binary Search Tree

LeetCode Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.


这一题和之前的LeetCode Convert Sorted Array to Binary Search Tree思路是一样的,只是把数组换成了链表,这样的话,就不能通过下标直接访问到中点元素了。
此时只能通过遍历找到链表的中点,然后以中点为根节点建树,最后分割左右链表,递归建树。完整代码如下:

class Solution {
public:
	TreeNode* sortedListToBST(ListNode* head) {
		if (head == NULL)return NULL;
		if (head->next == NULL)return new TreeNode(head->val);
		int n = 0, cnt = 0;
		ListNode * tmp = head;
		while (tmp != NULL) {
			n++;
			tmp = tmp->next;
		}
		tmp = head;
		while (cnt < n / 2 - 1) {
			tmp = tmp->next;
			cnt++;
		} // 此时tmp是中间节点的上一个节点
		TreeNode *root = new TreeNode(tmp->next->val);
		ListNode *head2 = tmp->next->next;
		tmp->next = NULL; // 断开
		root->left = sortedListToBST(head);
		root->right = sortedListToBST(head2);
		return root;
	}
};

本代码提交AC,用时22MS。击败了87%的人:-)
后来想想这题会不会有更优的解法,网上看了一下,发现自己蠢到哭了,链表找中点居然用了这么笨的方法,之前的快慢指针都忘了。换上快慢指针找链表中点的解法如下:

class Solution {
public:
	TreeNode* sortedListToBST(ListNode* head) {
		if (head == NULL)return NULL;
		if (head->next == NULL)return new TreeNode(head->val);
		ListNode *fast = head, *slow = head, *prior = head;
		while (fast->next != NULL && fast->next->next != NULL) {
			prior = slow;
			slow = slow->next;
			fast = fast->next->next;
		} // 此时slow为中间节点,prior为中间节点的上一个节点
		TreeNode *root = new TreeNode(slow->val);
		ListNode *head2 = slow->next;
		prior->next = NULL; //断开
		if (head != slow) root->left = sortedListToBST(head);
		root->right = sortedListToBST(head2);
		return root;
	}
};

本代码提交AC,用时26MS,有点失望,按理说这种解法是要比我上面的解法快的。
后来我又发现,这两种解法构建出来的平衡二叉搜索树不一样,如下图所示,但是他们都还算紧凑,都是正确的,看来答案不唯一啊。(其实主要是偶数长度时,有两个中间节点,选哪个都是正确的。)

LeetCode Rotate List

LeetCode Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.


这一题要把链表的后k个右旋到开头,其实就是把后k个节点断开,然后接到开头。思路是先遍历一遍得到链表长度n,然后k=k%n。再从头开始找第n-k-1个,断开然后拼接到开头即可。
完整代码如下:

class Solution {
public:
	ListNode* rotateRight(ListNode* head, int k) {
		if (head == NULL || head->next == NULL || k==0)return head;
		int n = 1, cut_pos = 0;
		ListNode* tail = head;
		while (tail->next != NULL) {
			n++;
			tail = tail->next;
		}
		//while (k >= n)k -= n;
		k = k%n;
		if (k == 0)return head;
		ListNode* new_tail = head;
		while (cut_pos + k + 1< n) {
			new_tail = new_tail->next;
			cut_pos++;
		}
		ListNode* new_head = new_tail->next;
		new_tail->next = NULL;
		tail->next = head;
		return new_head;
	}
};

本代码提交AC,用时20MS。
还可以其他一些思路,比如把连接头尾相连成一个环,然后找到断开的位置;或者使用快慢指针找到需要断开的位置,快指针先走k步,满指针再从头开始走,当快指针到末尾时,慢指针就到断开位置了。其实吧,我觉得直接找第n-k-1的位置,应该不比快慢指针慢吧,不知道为什么我这个花了20MS。

LeetCode Remove Nth Node From End of List

LeetCode Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,

   Given linked list: 1->2->3->4->5, and n = 2.
   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.


给定一个链表,要求删除倒数第n个元素。我想到的做法是遍历一遍链表,同时把链表每个元素保存到一个数组中,遍历完之后就知道链表长度,这样就可以计算出倒数第n个元素是哪个元素,然后直接删掉即可。
代码如下:

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		if (head->next == NULL) return NULL;
		vector<ListNode*> nodes;
		ListNode* ln = head;
		while (ln) {
			nodes.push_back(ln);
			ln = ln->next;
		}
		int target = nodes.size() - n;
		if (target == 0) {
			head->next = NULL;
			head = nodes[target + 1];
		}
		else if (target == nodes.size() - 1) {
			nodes[target - 1]->next = NULL;
		}
		else {
			nodes[target - 1]->next = nodes[target + 1];
		}
		return head;
	}
};

本代码提交AC,用时8MS。一看排名倒数,肯定还有更高效的算法,因为这种解法需要保存链表,而且是用vector.push_back的,所以肯定耗时。看题解,原来这是典型的快慢指针题,我这个非ACMer还是反应迟钝呀。
我们维护一个快指针和慢指针,初始的时候快慢都在起点,然后快指针先跑n步,此时快慢指针的距离为n,然后快慢指针同时跑,这样就能保持距离为n,当快指针到达末尾(NULL)的时候,慢指针刚好是在倒数第n的位置,真是巧妙。
但是为了删除倒数第n个节点,需要知道其前一个节点,所以让快指针到达NULL的前面位置停,即faster->next==NULL的时候停下来。
完整代码如下:

class Solution {
public:
	ListNode* removeNthFromEnd(ListNode* head, int n) {
		if (head == NULL ||  head->next == NULL) return NULL;
		ListNode* slower = head, *faster = head;
		while (n--) {
			faster = faster->next;
		}
		if (faster == NULL)return head->next;
		while (faster->next) {
			faster = faster->next;
			slower = slower->next;
		}
		slower->next = slower->next->next;
		return head;
	}
};

本代码提交AC,用时4MS,果然快了不少。