2020-06-23

LeetCode-链表相关

给出链表结点的定义：

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

从数组构造一个链表：


// create a linkedList from a vector
ListNode* createList(vector<int>& nums) {
    ListNode* tail = nullptr;
    for (int i = nums.size() - 1; i >= 0; i--) {
        ListNode* tmpNode = new ListNode(nums[i], tail);
        tail = tmpNode;
    }
    return tail;
}

补充递归

从链表到树的递归操作，体会递归从上到下，执行从底向上。

// traverse a list
void printListRecurvely(ListNode* head) {
    if (head == nullptr) return;
    printListRecurvely(head->next);
    cout << head->val << "->";

    return;
}

void inOrderTraverse(TreeNode* root) {

    if (root == nullptr) return;
    cout << root->val << ", ";
    inOrderTraverse(root->left);
    inOrderTraverse(root->right);

    return;
}

206 翻转整个链表

思路一与#92的翻转子操作相似，定义三个指针，并初始化，在移动到链表尾部的过程中改变next指针的指向，从而实现翻转链表。

实现：

// # 206 翻转整个链表
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* left = nullptr;
    ListNode* mid = head;
    ListNode* right = head->next;

    while (right != nullptr) {
        // operation
        mid->next = left;
        // move ptrs
        left = mid;
        mid = right;
        right = right->next;       
    }
    mid->next = left;
    return mid;
}

思路二：递归实现，从最后一个结点开始向前指向，最终返回最后一个结点。实现如下：

ListNode* reverseList(ListNode* head){
    if(!head || !head->next) return head;
    ListNode* p = reverseList(head->next);

    head->next->next = head;
    head->next = nullptr;
    return p;
}

其过程图示见笔记本。

分析递归返回值：返回值p始终指向原始链表的尾结点，而它又正好是翻转后的头结点。

92 翻转链表两个位置间的结点，部分翻转

例：

1 2	Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL

思路：先实现翻转连个结点间的结点，作为子造作，后移动指针，找到对应的m和n，调用子操作。

//# 92 翻转链表某个部分
class Sol92 {
private:
    /// reverse node from head to tail
    ListNode* reverseList(ListNode* head, ListNode* tail) {
        ListNode* pre = tail;
        ListNode* cur = head;
        while (cur != tail) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

对于对整个链表的翻转，上述函数参数tail为nullptr，即表示链表结尾的结点。

public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        assert(m <= n);
        // if (!head) return head;
        // if (m==n) return head;

        ListNode* dhead = new ListNode(-1, head);

        ListNode* nodeM = dhead;
        for (int i = 0; i < m; i++)
            nodeM = nodeM->next;

        ListNode* nodeN = dhead;
        for (int i = 0; i < n + 1; i++)
            nodeN = nodeN->next;

        ListNode* subHead = dhead;
        for (int i = 0; i < m - 1; i++)
            subHead = subHead->next;

        subHead->next = reverseList(nodeM, nodeN);

        return dhead->next;
    }
};

过程示意图见笔记本。

142 判断链表是否有环，若有则返回环的起点

思路一：在纸上比划比划，找规律。当快慢两指针相遇时，慢指针和entry指针同时向后移动，直到两者相遇，此时两指针所指向的就是环的起点。

思路二：首先判断是否有环，然后快慢指针在若干步后相遇（相遇时慢指针所走的步数正好是环中的节点数）。最后让新指针从头开始，慢指针从相遇位置开始，一起移动知道两者相遇，此时的相遇结点就是环的入口。

两思路其实是一样的。

实现：

class Sol142{
public:
	ListNode* entryPoint(ListNode* head){
		if (head == nullptr || head->next == nullptr)
			return nullptr;
		ListNode* dhead = new ListNode(-1, head);
		ListNode* fast = dhead;
		ListNode* slow = dhead;
		ListNode* entry = dhead;
		while(fast->next && fast->next->next ){
			fast = fast->next->next;
			slow = slow->next;
			if (slow == fast){ // 表示有环
                // slow和entry同时移动，直到两者相遇，相遇点就是
                // 环的起点
				while(slow != entry){
					slow = slow->next;
					entry = entry->next;
				}
				return entry;
			}
		}
		return nullptr;
	}
};

61 切断链表后再接上

描述：

翻转链表，从右边第k个位置切断，交换两部分位置，后将两部分接上，返回新的链表。

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

思路：

初始化所有指针，后移到其应该在的位置，最后重新链接两部分。就是指针操作。

实现：

class Sol61 {
public:
    ListNode* rotateRight(ListNode* head, int k) {
		if (head==nullptr) return head;
        //1. get the length of list
		ListNode* curr = head;
		int length=1;
		while(curr->next){
			curr = curr->next;
			length++;
		}
        // 注意这里，
		int newK = k%length;
		if (newK == 0) return head;

		//2. init ptrs
		ListNode* dhead = new ListNode(-1, head);
		ListNode* end = dhead;
		for (int i=0;i<newK;i++){
			end=end->next;
		}
		ListNode* pre = dhead;
		ListNode* newHead = head;
		while(end->next){
			end=end->next;
			pre=pre->next;
			newHead=newHead->next;
		} 
		//3. move ptrs
		pre->next = nullptr;
		end->next = head;

		//4. clean up
		delete dhead;
		dhead=nullptr;

		return newHead;
    }
};

328 奇数号结点链表，偶数号结点链表

描述：

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.

思路：遍历结点，更改结点next指针，奇数结点相连，偶数结点相连，最后将偶数节点链表的头接在奇数结点链表的尾。示意图见笔记。

实现：

class Sol328 {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;

		ListNode* odd = head;
		ListNode* oddCur = head;
		ListNode* even = head->next;
		ListNode* evenCur = head->next;

		while( true ){
			// 奇数个结点
			if (oddCur->next==nullptr && evenCur==nullptr){
				oddCur->next = even;
				break;
			}
            // 偶数个结点
			if (oddCur->next->next==nullptr && evenCur->next==nullptr){
				oddCur->next = even;
				break;
			} 
			
			oddCur->next = oddCur->next->next;
			oddCur = oddCur->next;
			
			evenCur->next = evenCur->next->next;
			evenCur = evenCur->next;
		}
		return odd;
    }
};

时间复杂度： O(N)

很直接的解法，但花了好长时间: 原因 1.测试vector马虎了；2.多个if判断的顺序问题。

重点在这儿，如果上述code中这两个if调换顺序：

// 奇数个结点
if (oddCur->next->next==nullptr && evenCur->next==nullptr){
    oddCur->next = even;
    break;
} 
// 偶数个结点
if (oddCur->next==nullptr && evenCur==nullptr){
    oddCur->next = even;
    break;
}

那么当结点个数为奇数个，且到链表尾时，第一个if语句中oddCur->next->next==nullptr就会出错，因为oddCur->next->next指向未定义的位置。所以总是出现Segmentation fault (core dumped)。！！！

注意:

多个if判断的顺序不是随意的。
如果在中间某处找不到错误，那么从头开始再找，别马虎。

430 扁平化一个多层链表

描述：给出一个结点定义：

class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};

并构造一个多层链表，目标是将这个多层链表变为一层，如下：

input：
1 - 2 - 3 - 4 - 5 - null
    |
    6 - 7 - 8 - 9 - null
            |
            10 - 11 - null
            
output:
1 - 2 - [6 - 7 - 8 - [10 - 11] - 9] - 3 - 4 - 5 - null

思路：

在循环的过程中改变了循环的对象，所以可以将所有深度的结点遍历到。这是由浅入深的扁平化过程。

遇到第一个含有child的结点后：
1 - 2 - 6 - 7 - 8 - 9 - 3 - 4 - 5 - null
                |
                10 - 11 - null

遇到第二个含有child的结点后：
1 - 2 - 6 - 7 - 8 - 10 - 11 - 9 - 3 - 4 - 5 - null

实现：

Node* flatten(Node* head) {
    for (Node* h = head; h; h = h->next){
        if (h->child){
            Node* next = h->next;
            h->next = h->child;
            h->next->prev = h;
            h->child = NULL;
            Node* p = h->next;
            while (p->next) p = p->next;
            p->next = next;
            if (next) next->prev = p;
        }
    }
    return head;
}