链表

链表

相关知识及题目

Posted by AIaimuti on November 20, 2019

面试时链表解题的方法论

  1. 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
  2. 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

链表相关题目主要就是两个思路

  1. 使用辅助空间，数组，哈希表等

  2. 使用快慢指针。

哈希表简单介绍

  1. 哈希表在使用层面上可以理解为一种集合结构
  2. 如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫UnOrderedSet)
  3. 如果既有key，又有伴随数据value，可以使用HashMap结构(C++中叫UnOrderedMap)
  4. 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
  5. 使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大
  6. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
  7. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小.
  8. C++ std unordered_set(unordered_map) 增：unordered_set::insert 查：unordered_set::find 删：unordered_set::erase

有序表简单介绍

  1. 有序表在使用层面上可以理解为一种集合结构
  2. 如果只有key，没有伴随数据value，可以使用TreeSet结构(C++中叫OrderedSet)
  3. 如果既有key，又有伴随数据value，可以使用TreeMap结构(C++中叫OrderedMap)
  4. 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
  5. 有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
  6. 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
  7. 放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
  8. 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用是这个东西内存地址的大小
  9. 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度（O(N * logN)）

有序表的固定操作

  1. voidput(Kkey,Vvalue)：将一个（key，value）记录加入到表中，或者将key的记录更新成value。
  2. Vget(Kkey)：根据给定的key，查询value并返回。
  3. voidremove(Kkey)：移除key的记录。
  4. booleancontainsKey(Kkey)：询问是否有关于key的记录。
  5. KfirstKey()：返回所有键值的排序结果中，最左（最小）的那个。
  6. KlastKey()：返回所有键值的排序结果中，最右（最大）的那个。
  7. KfloorKey(Kkey)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的前一个。
  8. KceilingKey(Kkey)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的后一个。

以上所有操作时间复杂度都是O(logN)，N为有序表含有的记录数

题目整理

1、反转单向和双向链表 （leetcode 206）

迭代方法时间复杂度为O（n）,空间复杂度O（1），递归方法时间复杂度为O（n）,空间复杂度O（n）不做整理了

反转单向链表

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//等号都是拷贝链表本身，cur->next 这类带next的是链表的连接
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* new_head = NULL;
        while (cur){
            ListNode* temp = cur->next;  
            cur->next = new_head;        
            new_head = cur;              
            cur = temp;
        }
        return new_head;
    }
};

反转双向链表

/*
struct ListNode{
    ListNode* pre;
    int val;
    ListNode* next;
};*/

class Solution {
public:
    ListNode* reverseList(ListNode* head){
        ListNode* cur = head, *p_pre = NULL;   
        while (cur){                           
            ListNode* p_next = cur->next;   //首先令p_next指向cur->next;
            cur->next = p_pre;              //cur->next的断开，指向cur->pre
            cur->pre = p_next;              //cur->pre的断开，连接p_next，完成当前结点的前后指针反转
            p_pre = cur;                    //反转完成，后移p_pre指针。
            cur= p_next;                    //后移cur指针。
        }
        return p_pre;    //当cur为Null时，说明已经反转完毕，它的前一节点pre指向尾节点。返回此节点指针。
    }
};

2、打印两个有序链表的公共部分

不相等的部分小者向后移动，相等的部分打印

void sol(list_node * a_head, list_node * b_head)
{
    //////在下面完成代码
    while (a_head && b_head){
        if(a_head->val < b_head->val){
            a_head = a_head->next;
        }
        else if (a_head->val > b_head->val){
            b_head = b_head->next;
        }
        else if (a_head->val  == b_head->val ){
            cout << a_head->val << " ";
            a_head = a_head->next;
            b_head = b_head->next;
        }
    }
}

3、判断一个链表是否为回文结构 （leetcode 234）

使用栈，将链表元素放入栈内，如果遇见相同的就弹出，最后栈为空则为回文结构，O（n）,空间复杂度O（n）

代码

#include <stack>
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL){
            return true;
        }
        ListNode* cur = head;
        stack <int> s;
        while (cur){  
                s.push(cur->val);
                cur = cur->next;
            }
        cur = head;
        while (cur){
            if (s.top() == cur->val){
                s.pop();
            }
            cur = cur->next;
        }
        return s.empty();
    }
};
  • 使用快慢指针原地修改链表,额外空间复杂度O（1）
using namespace std;
class PalindromeList {
public:
    bool chkPalindrome(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return true;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
        }
        slow = reverseList(slow->next);
        while (slow != NULL) {
            if (head->val != slow->val) {
                return false;
            }
            head = head->next;
            slow = slow->next;
        }
        return true;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* here = head;
        while (here!=NULL) {
            ListNode* temp = here->next;
            here->next = pre;
            pre = here;
            here = temp;
        }
        return pre;
    }
};

4、将单向链表按某值划分成左边小，中间相等，右边大的形式 (leetcode 86题分为大小区，与本题类似但要简单)

题目：给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。除这个要求外，对调整后的节点顺序没有更多的要求。 ** 辅助数组**

将链表内容放入数组中，再利用快速排序partition的思路进行划分。

#include <vector>
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == NULL || head->next == NULL) {
			return head;
		}
        //变成数组
        int i = 0;
		ListNode* cur = head;
        vector <ListNode*> arr;
		while (cur) {
            i++;
            arr.push_back(cur);
			cur = cur->next;
		}
		arrPartition(arr, x);
		for (i = 1; i != arr.size(); i++) {
		    arr[i - 1]->next = arr[i];
        }
        arr[i - 1]->next = NULL;
        return arr[0];
	}
 
	void arrPartition(vector <ListNode*>& nodeArr, int pivot) {
		int small = -1;
		int big = nodeArr.size();
		int index = 0;
		while (index < big) {
			if (nodeArr[index]->val < pivot) {
				swap(nodeArr[++small], nodeArr[index++]);
			} 
           		 else if (nodeArr[index]->val  == pivot) {
				index++;
			} 
			else {
				swap(nodeArr[index],nodeArr[--big]);
			}
		}
	}
};

进阶：要求额外空间复杂为O(n)，且相对位置不变(即具有稳定性)

    ListNode* partition(ListNode* head, int x) {
        ListNode* sH = NULL;
        ListNode* sT = NULL;
        ListNode* eH = NULL;
        ListNode* eT = NULL;
        ListNode* bH = NULL;
        ListNode* bT = NULL;
        ListNode* next = NULL;
        while (head) {
            next = head->next;
            head->next = NULL;
            if (head->val < x) {
                if (sH == NULL) {
                    sT = head;
                    sH = head;
                }
                else {
                    sT->next = head;
                    sT = head;
                }
            }
            else if (head->val > x) {
                if (bH == NULL) {
                    bH = head;
                    bT = head;
                }
                else {
                    bT->next = head;
                    bT = head;
                }
            }
            else{
                if (eH == NULL) {
                    eH = head;
                    eT = head;
                }
                else {
                    eT->next = head;
                    eT = head;
                }
            }
            head = next;
        }
        if (sT) {
            sT->next = eH;
            eT = eT == NULL ? sT : eT;
        }
        if (eT != NULL) {
            eT->next = bH;
        }
        return sH != NULL ? sH : eH != NULL ? eH : bH;
    }

5、复制含有随即指针节点的链表 (leetcode 138)

1、哈希表

1、先保存每个节点的val

2、再进行next，random信息的拷贝

时间复杂度：O(n) 空间复杂度：O(n)

#include <unordered_map>
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return head;
        }
        unordered_map <Node*,Node*> map;
        Node* cur = head;
        while (cur){
            Node *copy = new Node(cur->val);
            map[cur] = copy;
            cur = cur->next;
        }
        cur = head;
        while (cur){
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        return map[head];    
    }
};

2、原地复制

1、复制节点，同时将复制节点链接到原节点后面，如A->B->C 变为 A->A’->B->B’->C->C’。

2、设置节点random值。

3、将复制链表从原链表分离。

时间复杂度：O(n) 空间复杂度：O(1)

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return head;
        }
        Node *node = head;
        //1. 将复制节点添加到原节点后面
        while (node) {
            Node *copy = new Node(node->val, nullptr, nullptr);
            copy->next = node->next;
            node->next = copy;
            node = copy->next;
        }
        
        //2. 复制random节点
        node = head;
        while (node) {
            if (node->random) {
                node->next->random = node->random->next;
            }            
            node = node->next->next;
        }
        
        //3. 分离链表
        node = head;
        Node *newHead = head->next;
        Node *newNode = newHead;
        while (node) {
            node->next = node->next->next;     
            if (newNode->next) {
                newNode->next = newNode->next->next;            
            }            
            node = node->next;
            newNode = newNode->next;
        }
        return newHead;
    }

};

6、环型链表 (leetcode 141)

1、哈希表储存结点，发现相同的即为有环，时间复杂度O(n),空间复杂度O(n)

class Solution {
public:
    bool hasCycle(ListNode *head) {
        set <ListNode*> hash;
        while (head){
            if (hash.find(head) != hash.end()){
                return true;
            }
            else{
                hash.insert(head);
                head = head->next;
            }
        }
        return false;
    }
};

2、快慢指针

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

CATALOG
    FEATURED TAGS
    C++ 操作系统 O(N * logN) Unity 3D 入门 Unity 3D 初级 UE4 入门系列 UE4 蓝图实现FPS系列 计算机网络 UE4 C++入门系列