Tag Archives: 链表

剑指 Offer 36. 二叉搜索树与双向链表

剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

为了让您更好地理解问题,以下面的二叉搜索树为例:

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

注意:本题与主站 426 题相同:https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意:此题对比原题有改动。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


如何将二叉搜索树转换in-place转换为有序双向链表。

此题同时考察了多个知识点,首先二叉搜索树转换为有序结果,需要使用二叉树的中序遍历,然后要in-place转换为双向链表,则需要在遍历二叉树的过程中,对每个节点,修改其left和right指针,使其分别指向转换后的双向链表的前驱和后继节点。

使用递归的方法,设置两个全局变量pre和head,分别表示当前遍历节点的前驱节点,以及转换后的双向链表的头结点。完整代码如下:

class Solution {
private:
    Node *pre, *head;
    void DFS(Node *root) {
        if(root == NULL) return;

        DFS(root->left);
        if(head == NULL) head = root;
        else pre->right = root;
        
        root->left = pre;
        pre = root;
        DFS(root->right);
    }
public:
    Node* treeToDoublyList(Node* root) {

        if(root == NULL) return NULL;

        pre = head = NULL;

        DFS(root);

        head->left = pre;
        pre->right = head;

        return head;
    }
};

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

剑指 Offer 06. 从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2]
输出:[2,3,1]
 

限制:

0 <= 链表长度 <= 10000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个单链表,从尾到头打印链表的值。先顺序遍历链表,将结果存到一个数组中,然后逆序数组。代码如下:

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if(head == NULL) return {};
        vector<int> ans;
        while(head != NULL) {
            ans.push_back(head->val);
            head = head->next;
        }
        int i = 0, j = ans.size() - 1;
        while(i < j) {
            swap(ans[i++], ans[j--]);
        }
        return ans;
    }
};

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

LeetCode First Unique Number

LeetCode First Unique Number

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

  • FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
  • int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
  • void add(int value) insert value to the queue.

Example 1:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 

[null,2,null,2,null,3,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2);            // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3);            // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1

Example 2:

Input: 
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output: 

[null,-1,null,null,null,null,null,17]

Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17

Example 3:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output: 

[null,809,null,-1]

Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1

Constraints:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^8
  • 1 <= value <= 10^8
  • At most 50000 calls will be made to showFirstUnique and add.

设计题。设计一个队列,能够快速返回当前队列中第一个unique的数。

和之前的LRU很类似,使用list+unordered_map实现。list保存当前unique的数,unordered_map保存每个unique的数在list中的迭代器。当插入一个数到队列中时,首先看看在不在unordered_map中,如果不在,说明这个数是unique的,插入list和unordered_map。如果在,则看看unordered_map中的迭代器,如果迭代器不为空,说明这个数之前是unique的,需要从list中删掉;否则说明这个数之前就已经不是unique的了,不做任何操作。

完整代码如下:

class FirstUnique {
private:
	list<int> uniques_;
	unordered_map<int, list<int>::iterator> hash;
public:
	FirstUnique(vector<int>& nums) {
		for (int i = 0; i < nums.size(); ++i) {
			add(nums[i]);
		}
	}

	int showFirstUnique() {
		if (uniques_.empty())return -1;
		else return uniques_.front();
	}

	void add(int value) {
		if (hash.find(value) == hash.end()) {
			uniques_.push_back(value);
			hash[value] = --uniques_.end();
		}
		else {
			if (hash[value] != uniques_.end()) {
				uniques_.erase(hash[value]);
				hash[value] = uniques_.end();
			}
		}
	}
};

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

LeetCode Queries on a Permutation With Key

1409. Queries on a Permutation With Key

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

  • In the beginning, you have the permutation P=[1,2,3,...,m].
  • For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].  

Example 2:

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Example 3:

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]

Constraints:

  • 1 <= m <= 10^3
  • 1 <= queries.length <= m
  • 1 <= queries[i] <= m

初始时给定一个P=[1,2,…,m]的数组,然后有一个queries数组,对于每一个query,问其在P中的下标,并且将该元素移到P的开头,最后问queries数组中所有query的下标的数组。

模拟题,由于有元素的移动操作,即删除和插入操作,所以这里借用链表来处理。完整代码如下:

class Solution {
public:
	vector<int> processQueries(vector<int>& queries, int m) {
		list<int> lst;
		for (int i = 1; i <= m; ++i)lst.push_back(i);
		vector<int> ans;
		for (int i = 0; i < queries.size(); ++i) {
			int val = queries[i];
			int j = 0;
			list<int>::iterator it = lst.begin();
			while (it != lst.end()) {
				if (*it == val) {
					ans.push_back(j);
					lst.erase(it);
					lst.push_front(val);
					break;
				}
				else {
					++it;
					++j;
				}
			}
		}
		return ans;
	}
};

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

LeetCode Middle of the Linked List

876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

  • The number of nodes in the given list will be between 1 and 100.

给定一个单向链表,要求找到其中间节点。

简单题,快慢指针,快指针的速度是慢指针的2倍,则当快指针走到末尾时,慢指针正好指向中间位置。代码如下:

class Solution {
public:
	ListNode* middleNode(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *fast = head, *slow = head;
		while (fast->next) {
			fast = fast->next->next;
			slow = slow->next;
			if (fast == NULL)break;
		}
		return slow;
	}
};

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

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取出来就好了。其他粒度也是类似的。 完整代码如下: [cpp] 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; } }; [/cpp] 本代码提交AC,用时19MS。]]>

LeetCode LRU Cache

146. 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.

The cache is initialized with a positive capacity.

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

148. Sort List

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

本题要求用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。

二刷,归并排序还可以写得简单点:

class Solution {
public:
	ListNode* sortList(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *slow = head, *fast = head, *pre = head;
		while (fast != NULL && fast->next != NULL) {
			pre = slow;
			slow = slow->next;
			fast = fast->next->next;
		}
		pre->next = NULL;
		ListNode *left = sortList(head), *right = sortList(slow);
		ListNode *dummy = new ListNode(0);
		ListNode *lst = dummy;
		while (left != NULL || right != NULL) {
			int l = left != NULL ? left->val : INT_MAX;
			int r = right != NULL ? right->val : INT_MAX;
			if (l < r) {
				lst->next = left;
				left = left->next;
			}
			else {
				lst->next = right;
				right = right->next;
			}
			lst = lst->next;
		}
		return dummy->next;
	}
};

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

LeetCode Reorder List

143. Reorder List

Given a singly linked list LL0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->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

138. 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.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

  • -10000 <= Node.val <= 10000
  • Node.random is null or pointing to a node in the linked list.
  • Number of Nodes will not exceed 1000.

本题要求对一个链表进行深度拷贝。这个链表有一个特点就是除了有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,居然比前面的还慢。。。

三刷。和上面的解法相同,代码更易读:

class Solution {
public:
	Node* copyRandomList(Node* head) {
		if (head == NULL)return NULL;

		// 拷贝主干节点
		Node *l1 = head;
		while (l1 != NULL) {
			Node *cur = new Node(l1->val);
			cur->next = l1->next;
			l1->next = cur;
			l1 = cur->next;
		}

		//连接random指针
		l1 = head;
		while (l1 != NULL) {
			if (l1->random != NULL) {
				l1->next->random = l1->random->next;
			}
			l1 = l1->next->next;
		}

		//拆分
		l1 = head;
		Node *new_head = l1->next;
		Node *l2 = new_head;
		while (l1 != NULL) {
			l1->next = l2->next;
			if (l1->next != NULL) {
				l2->next = l1->next->next;
			}
			l1 = l1->next;
			l2 = l2->next;
		}
		return new_head;
	}
};

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