Tag Archives: 链表

LeetCode Design Log Storage System

LeetCode Design Log Storage System
You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.
Design a log storage system to implement the following functions:
void Put(int id, string timestamp): Given a log's unique id and timestamp, store the log in your storage system.
int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", granularity = "Day", it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.
Example 1:

put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note:

  1. There will be at most 300 operations of Put or Retrieve.
  2. Year ranges from [2000,2017]. Hour ranges from [00,23].
  3. Output for Retrieve has no order required.

设计一个日志系统,该系统有两个操作,put(id,timestamp)把timestamp时刻的日志id放到日志系统中,retrieve(start,end,gra)从系统中取出timestamp范围在[start,end]之间的日志id,时间的粒度是gra。
我设计的系统是这样的,为了方便retrieve,系统中的日志都按timestamp排序了。有趣的是,在zero-padded(每部分不足补前导0)的情况下,timestamp的字符串排序就是timestamp表示的时间的排序。
定义一个Node结构体,保持一个日志,信息包括日志id和timestamp。用一个链表存储所有Node,并且当新Node插入时,采用插入排序的方法使得链表始终有序。
retrieve的时候,根据粒度,重新设置start和end,比如样例中粒度为Year时,把start改为Year固定,其他时间最小

"2016:00:00:00:00:00"

把end改为Year固定,其他时间最大

"2017:12:31:23:59:59"

这样我只需要遍历链表,把所有timestamp字符串在这个范围内的日志id取出来就好了。其他粒度也是类似的。
完整代码如下:

class LogSystem {
private:
	struct Node {
		int id;
		string timestamp;
		Node(int i, string t) :id(i), timestamp(t) {};
	};
	list<Node> log;
	string start, end;
public:
	LogSystem() {
		start = "2000:00:00:00:00:00";
		end = "2017:12:31:23:59:59";
	}
	void put(int id, string timestamp) {
		Node node(id, timestamp);
		if (log.empty())log.push_back(node);
		else {
			auto it = log.begin();
			while (it != log.end() && (*it).timestamp <= timestamp)++it;
			log.insert(it, node);
		}
	}
	vector<int> retrieve(string s, string e, string gra) {
		if (gra == "Year") {
			s = s.substr(0, 4) + start.substr(4);
			e = e.substr(0, 4) + end.substr(4);
		}
		else if (gra == "Month") {
			s = s.substr(0, 7) + start.substr(7);
			e = e.substr(0, 7) + end.substr(7);
		}
		else if (gra == "Day") {
			s = s.substr(0, 10) + start.substr(10);
			e = e.substr(0, 10) + end.substr(10);
		}
		else if (gra == "Hour") {
			s = s.substr(0, 13) + start.substr(13);
			e = e.substr(0, 13) + end.substr(13);
		}
		else if (gra == "Minute") {
			s = s.substr(0, 16) + start.substr(16);
			e = e.substr(0, 16) + end.substr(16);
		}
		vector<int> ans;
		auto it = log.begin();
		while (it != log.end() && (*it).timestamp < s)++it;
		while (it != log.end() && (*it).timestamp <= e) {
			ans.push_back((*it).id);
			++it;
		}
		return ans;
	}
};

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

LeetCode LRU Cache

LeetCode LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

实现一个LUR cache。
我们知道数据的访问都有时间局部性和空间局部性,所以为了加快访问速度,把经常访问的数据放到高速缓存cache中,这样先查cache,不命中再查内存或者外存。
但是cache一般都很小,当新数据需要插入cache时,如果cache满,则需要替换掉cache中旧的元素。此时替换哪个元素就有很多策略了,可以把最久没访问的替换出去,也可以把访问频率最低的替换出去,还可以把最先进入的替换出去等等,各种策略就形成了不同的缓存替换算法。
LRU的意思是Least Recently Used (LRU),即把最近最久没访问的元素替换出去,是指时间上最久没访问的,而不是频率上访问最少的哦。
题目要求实现LRU的两个接口,分别是

  1. get(key),从LRU中获取key对应的value,如果LRU中不存在key,则返回-1
  2. put(key,value),把key和对应的value插入到LRU中,如果LRU满,则要替换掉最近最久没访问的元素

要求这两个操作都在O(1)时间内完成。
我们来分析一下应该用哪些数据结构使这两个操作都在O(1)时间内完成。首先get需要在O(1)时间内判断key是否在LRU中,所以可能需要用hash来存储<key,value>对。其次,需要缓存替换时,要在O(1)时间内把最久没访问的<key,value>删掉,同时插入新的<key,value>,删除和插入能在O(1)时间内完成的就是链表了。
综合上面的分析,我们可以用unordered_map+list来实现LRU,STL的list是一个双向链表。
参考这份代码。我们使用list<int> used来保存当前在LRU中的那些key,注意是key;用unordered_map<int, pair<int, list<int>::iterator>> cache来保存真实的缓存,cache的key就是LRU中现存的key,value是一个pair,保存了key对应的value,以及这个key在链表中的迭代器(指针)。两个操作的实现如下:
put(key,value)。每当有新<key,value>进入时,如果key已经在cache中,则只需要更新key对应的value,同时,刚访问的元素下次很可能再次访问,所以需要把这个key提到链表的表头(为了不让这个key沉到表尾)。如果key不在cache中,但cache已满,则需要把链表尾部的key对应的数据在cache中删掉,同时也需要在链表中删掉这个尾节点;如果cache不满,则把新key插入到链表表头,同时把<key,value>插入到cache中,且key在链表中的位置是list.begin()。
get(key)。如果key不在cache中,直接返回-1。如果key在cache中,直接从cache中得到对应的value,同时根据迭代器,把key提到链表表头。
根据上述算法描述,我们需要抽象一个函数,moveToHead(list<int>::iterator &it),即把迭代器it指向的那个key移到表头,包括两个操作,把it从it位置删掉,把it的值插到表头。
完整代码如下:

class LRUCache {
private:
	unordered_map<int, pair<int, list<int>::iterator>> cache;
	list<int> used;
	int _capacity;
	// 把it节点**剪切**到表头
	void moveToHead(list<int>::iterator &it) {
		int key = *it;
		used.erase(it);
		used.push_front(key);
		cache[key].second = used.begin();
	}
public:
	LRUCache(int capacity):_capacity(capacity) {
	}
	int get(int key) {
		if (cache.find(key) == cache.end())return -1;
		int value = cache[key].first;
		moveToHead(cache[key].second);
		return value;
	}
	void put(int key, int value) {
		if (cache.find(key) != cache.end()) {
			cache[key].first = value;
			moveToHead(cache[key].second);
		}
		else {
			if (used.size() == _capacity) {
				cache.erase(used.back());
				used.pop_back();
			}
			used.push_front(key);
			cache[key] = { value,used.begin() };
		}
	}
};

本代码提交AC,用时96MS。
我们还可以自己实现list,就是一个双向链表。这个双向链表包括头结点head和尾节点tail。为了插入删除的方便,我们设置了一个用不到的head和tail,所以真正的数据其实是在head和tail之间的,如下,节点1~3才是真正的数据节点

头 --> 节 --> 节 --> 节 --> 尾
节     点     点     点     节
点 <-- 1  <-- 2 <-- 3  <-- 点

这里我们抽象出了3个函数,removeFromList和moveToHead完成上一种实现中的moveToHead功能,即先把节点从原链表中删除(相当于摘下来),然后把这个节点安放到表头(上图节点1)。removeTail就是在需要替换时,删除表尾节点(上图节点3)。
完整代码如下:

class LRUCache {
private:
	struct Node {
		int key, value;
		Node *pre, *next;
		Node(int k, int v) :key(k), value(v), pre(NULL), next(NULL) {};
	};
	unordered_map<int, Node*> cache;
	Node *head, *tail;
	int _capacity;
	// 从原链表中删除节点node(摘下)
	void removeFromList(Node *node) {
		node->pre->next = node->next;
		node->next->pre = node->pre;
	}
	// 把节点node放到“表头”(安放)
	void moveToHead(Node *node) {
		node->next = head->next;
		head->next->pre = node;
		node->pre = head;
		head->next = node;
	}
	// 删除“尾节点”
	void removeTail() {
		Node *target = tail->pre;
		target->pre->next = target->next;
		target->next->pre = target->pre;
		delete target;
	}
public:
	LRUCache(int capacity) :_capacity(capacity) {
		head = new Node(0, 0); // 辅助头结点
		tail = new Node(0, 0); // 辅助尾节点
		head->next = tail;
		tail->pre = head;
	}
	int get(int key) {
		if (cache.find(key) == cache.end())return -1;
		int value = cache[key]->value;
		removeFromList(cache[key]);
		moveToHead(cache[key]);
		return value;
	}
	void put(int key, int value) {
		if (cache.find(key) != cache.end()) {
			cache[key]->value = value;
			removeFromList(cache[key]);
			moveToHead(cache[key]);
		}
		else {
			if (cache.size() == _capacity) {
				cache.erase(tail->pre->key);
				removeTail();
			}
			Node *node = new Node(key, value);
			cache[key] = node;
			moveToHead(node);
		}
	}
};

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

LeetCode Sort List

LeetCode Sort List
Sort a linked list in O(n log n) time using constant space complexity.


本题要求用O(nlogn)的时间复杂度和常数空间复杂度对一个链表排序。
O(nlgn)的排序算法有快速排序、堆排序、归并排序,快排和堆排都需要对元素的随机访问,不适用于链表,这里我们可以用归并排序实现。
归并的思路是不断把链表对分成两个子链表,直到只剩一个节点,此时一个节点是有序的,然后不断的两两归并,mergeList就好办多了。
完整代码如下:

class Solution {
private:
	ListNode *mergeList(ListNode *h1, ListNode *h2) {
		if (!h1)return h2;
		else if (!h2)return h1;
		ListNode *head = new ListNode(0), *h = head;
		while (h1&&h2) {
			if (h1->val < h2->val) {
				h->next = h1;
				h1 = h1->next;
			}
			else {
				h->next = h2;
				h2 = h2->next;
			}
			h = h->next;
		}
		if (h1)h->next = h1;
		else if (h2)h->next = h2;
		return head->next;
	}
public:
	ListNode* sortList(ListNode* head) {
		if (!head || !head->next)return head;
		ListNode *slow = head, *fast = head;
		while (fast->next&&fast->next->next) {
			slow = slow->next;
			fast = fast->next->next;
		}
		fast = slow->next;
		slow->next = NULL;
		ListNode *left = sortList(head);
		ListNode *right = sortList(fast);
		return mergeList(left, right);
	}
};

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

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 Copy List with Random Pointer

LeetCode Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.


本题要求对一个链表进行深度拷贝。这个链表有一个特点就是除了有value和next指针,还有一个random指针随机指向链表中的一个节点。
我的解法是这样的,使用一个hash表记录每个节点的下标,并且用一个数组array_for_list存储新创建的链表。第一遍扫描只把value和next都复制好,同时记录hash和array_for_list。第二遍扫描时,看看原节点的random是否为空,如果不为空,则去hash表里找其random指向节点的下标pos,同时把新链表的random指向array_for_list[pos]节点。
完整代码如下:

class Solution {
public:
	RandomListNode *copyRandomList(RandomListNode *head) {
		unordered_map<RandomListNode*, int> hash;
		vector<RandomListNode*> array_for_list;
		RandomListNode *new_head = new RandomListNode(0), *h1 = head, *h2 = new_head;
		int idx = 0;
		while (h1) {
			hash[h1] = idx++;
			RandomListNode *node = new RandomListNode(h1->label);
			array_for_list.push_back(node);
			h2->next = node;
			h1 = h1->next;
			h2 = h2->next;
		}
		h1 = head;
		h2 = new_head->next;
		while (h1) {
			if (h1->random) {
				h2->random = array_for_list[hash[h1->random]];
			}
			h1 = h1->next;
			h2 = h2->next;
		}
		return new_head->next;
	}
};

本代码提交AC,用时52MS。
二刷。《剑指offer》上有一个类似的题,可以不用额外空间来做,即先对原数组的每个节点都拷贝一个插到原节点的后面,然后对于每一个原节点,新节点的random节点就是原节点random节点的下一个节点。很有意思,可以看《剑指offer》P147,或者看讨论区:https://discuss.leetcode.com/topic/7594/a-solution-with-constant-space-complexity-o-1-and-linear-time-complexity-o-n/64
完整代码如下:

class Solution {
public:
	RandomListNode *copyRandomList(RandomListNode *head) {
		if (head == NULL)return head;
		RandomListNode *iter = head;
		while (iter) {
			RandomListNode *node = new RandomListNode(iter->label);
			node->next = iter->next;
			iter->next = node;
			iter = node->next;
		}
		iter = head;
		while (iter) {
			if (iter->random) {
				iter->next->random = iter->random->next;
			}
			iter = iter->next->next;
		}
		iter = head;
		RandomListNode *copy_head = new RandomListNode(0); // dummy
		RandomListNode *copy_iter = iter->next, *copy_tail = copy_head;
		while (iter) {
			copy_tail->next = copy_iter;
			copy_tail = copy_tail->next;
			iter->next = copy_iter->next;
			iter = iter->next;
			if (iter) {
				copy_iter->next = iter->next;
				copy_iter = copy_iter->next;
			}
		}
		return copy_head->next;
	}
};

本代码提交AC,用时65MS,居然比前面的还慢。。。

LeetCode Insertion Sort List

LeetCode Insertion Sort List
Sort a linked list using insertion sort.


对一个链表进行插入排序。
简单题,每次从原链表中断一个节点下来,然后在新的有序链表中线性查找插入的位置。这里有个技巧,有可能链表的第一个节点很大,后续节点需要插入表头;也可能后续节点很大,需要插入表尾;还可能是不大不小,插入中间。情况比较多,为了方便统一代码形式,可以在新的有序链表的表头插入一个INT_MIN的最小节点,这样所有代码都统一了,也不容易出错。
完整代码如下:

class Solution {
public:
	ListNode* insertionSortList(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *newHead = new ListNode(INT_MIN);
		newHead->next = head;
		head = head->next;
		newHead->next->next = NULL;
		while (head) {
			ListNode *insertPos = newHead->next, *pre = newHead;
			while (insertPos&&insertPos->val < head->val) {
				insertPos = insertPos->next;
				pre = pre->next;
			}
			ListNode *tmp = head;
			head = head->next;
			tmp->next = insertPos;
			pre->next = tmp;
		}
		return newHead->next;
	}
};

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

LeetCode Intersection of Two Linked Lists

LeetCode Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3

begin to intersect at node c1.
 
Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

给定两个链表,如果这两个链表在某个点相交,并且此后合并为一个链表,要找出这个交点;如果不想交,返回NULL。
简单的方法是,如果两个链表相交,比如题图在c1相交,则对于两个链表,从相交点往后长度是一样的,所以我们可以先求出两个链表的长度,假设长度差是delta,则较长链表先前进delta步,此时长短链表的往后的路都是一样长了,这样两个链表一起走,如果发现有相等的节点,则是相交节点,否则两个链表不相交。
本思路代码如下:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	int len1 = 0, len2 = 0;
    	ListNode *h1 = headA, *h2 = headB;
    	while(h1){
    		++len1;
    		h1 = h1->next;
    	}
    	while(h2){
    		++len2;
    		h2 = h2->next;
    	}
    	h1 = headA;
    	h2 = headB;
    	if(len1 > len2){
    		while(len1 > len2){
    			h1 = h1->next;
    			--len1;
    		}
    	} else if(len2 > len1) {
    		while(len2 > len1){
    			h2 = h2->next;
    			--len2;
    		}
    	}
    	while(h1 && h2 && h1 != h2){
    		h1 = h1->next;
    		h2 = h2->next;
    	}
    	if(!h1 || !h2)return NULL;
    	else return h1;
    }
};

本代码提交AC,用时39MS。
还有一种思路很巧妙,参考:http://www.cnblogs.com/yuzhangcmu/p/4128794.html
具体是这样的,比如题目中的例子,假设指针pA和pB分别指向A,B两个链表,两个指针同时不断的一步一步走,当pA走到结尾时,pA指向B链表表头开始走,同理当pB走到结尾时,pB指向A链表表头开始走。不断的走,当pA和pB指向同一个节点时,就是那个相交的节点。这个很巧妙呀,当pA和pB走到相交点时,他们走过的路程其实是相等的,比如题目中,他们都走了9个节点后相遇了。
代码如下:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    	if(headA == NULL || headB == NULL) return NULL;
    	ListNode *h1 = headA, *h2 = headB;
    	ListNode *tail1 = NULL, *tail2 = NULL;
    	while(true){
    		if(h1 == NULL) h1 = headB;
    		if(h2 == NULL) h2 = headA;
    		if(h1->next == NULL) tail1 = h1;
			if(h2->next == NULL) tail2 = h2;
    		if(tail1 != NULL && tail2 != NULL && tail1 != tail2) return NULL;
    		if(h1 == h2) return h1;
    		h1 = h1->next;
    		h2 = h2->next;
    	}
    }
};

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

LeetCode Flatten Binary Tree to Linked List

LeetCode Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.

Hints:If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.


把一棵二叉树展开成一个链表,链表还是借助树的数据结构,只不过是借用了树的右孩子指针作为链表的指针。
仔细观察发现新的链表的顺序和树的先序遍历的顺序一致,如果能使用额外的空间,则先序遍历后把节点存到数组中,然后依次链接起来。
如果不使用额外空间,则只能想办法在DFS时就建立好链接关系。先序遍历的顺序是根左右,但是这题为了方便,我们先对右孩子建立链表,然后把右孩子接到父亲的左孩子的最右下角的节点上。比如上图中,我们建立好5->6的链表之后,需要把它接到4号节点的右边。

         1
        /
       2
      / \
     3   4
          \
           5
            \
             6

所以针对右孩子,我们需要根据父节点找到父节点的左子树的最右下角的节点。但是针对左孩子时,因为此时右孩子已经建立好链表并且接到了左孩子正确的位置上,所以只需要把左孩子接到父亲的右孩子位置,并把原来的左孩子置空,下图就是把上图1的左子树放到了右边,左边置为空。

   1
     \
       2
      / \
     3   4
          \
           5
            \
             6

完整代码如下:

class Solution2 {
public:
	void dfs(TreeNode* par, TreeNode* cur) {
		if (cur == NULL)return;
		if(par){
			if (cur == par->right) {
				if (par->left) {
					TreeNode* tmp = par->left;
					while (tmp->right)tmp = tmp->right;
					tmp->right = cur;
					par->right = NULL;
				}
			}
			else {
				par->right = cur;
				par->left = NULL;
			}
		}
		if (cur->right)dfs(cur, cur->right);
		if (cur->left)dfs(cur, cur->left);
	}
	void flatten(TreeNode* root) {
		dfs(NULL, root);
	}
};

本代码提交AC,用时6MS。
还有一种思路比这简单,上面的解法需要while循环查找左兄弟的最右下角的节点,如果我们在DFS中直接返回尾节点,就不需要while查找了。
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了:
1
/    \
2     5
\       \
3      6 <- rightTail
\
4  <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list?显而易见:
leftTail->right = root->right;
root->right = root->left;
root->left = NULL;
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
代码如下:

class Solution {
public:
	TreeNode* dfs(TreeNode* root) {
		if (!root)return NULL;
		TreeNode* leftTail = dfs(root->left);
		TreeNode* rightTail = dfs(root->right);
		if (root->left) {
			leftTail->right = root->right;
			root->right = root->left;
			root->left = NULL;
		}
		if (rightTail)return rightTail;
		if (leftTail)return leftTail;
		return root;
	}
	void flatten(TreeNode* root) {
		dfs(root);
	}
};

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

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 Add Two Numbers II

LeetCode Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

有两个数字链表,分别存储了两个整数,要求把这两个整数加起来。和LeetCode Add Two Numbers的区别是,之前的链表最低位在表头,我们正常加法也是从低位到高位,所以之前的题可以直接从表头开始加。但是这个题稍有不同,最低位在表尾,表头是最高位,所以必须先跑到链表尾才能做加法。一种方法是我们可以先把链表逆序,这样就可以用之前的解法了,但是题目中说不能修改原链表,所以不能用这种解法。
那么怎样获取到表尾的数据进行加法呢,我们可以把两个链表压入两个堆栈,因为堆栈是后进先出,所以再次从栈顶取数据做加法的时候就是从低位到高位的加了。
完整代码如下:

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		stack<int> s1, s2;
		while (l1) {
			s1.push(l1->val);
			l1 = l1->next;
		}
		while (l2) {
			s2.push(l2->val);
			l2 = l2->next;
		}
		ListNode* ans = new ListNode(1); // 预设好的最高位进位:-)
		int sum = 0;
		while (!s1.empty() || !s2.empty()) {
			if (!s1.empty()) {
				sum += s1.top();
				s1.pop();
			}
			if (!s2.empty()) {
				sum += s2.top();
				s2.pop();
			}
			ListNode* tmp = new ListNode(sum%10);
			tmp->next = ans->next;
			ans->next = tmp;
			sum /= 10; // 下一次的进位
		}
		if (sum)return ans;
		else return ans->next;
	}
};

本代码提交AC,用时55MS。
代码中有两个地方解释一下,一般链表的题都会在结果链表中加一个没用的头结点,一般是0,但是因为最终的加法结果可能进位,所以把表头的值定为1,如果有进位,这个1也可以用上,如果没进位,就返回1的next。另一个就是我们没有单独定义add1、add2和carry,而是只用一个sum变量搞定了,sum%10相当于进位之后的结果,sum/10相当于进位。