【Leetcode刷题】（一）链表

总结：

1、链表中的每个节点至少包含两个部分：数据域与指针域；

2、链表中的每个节点，通过指针域的值，形成一个线性结构；

3、查找节点O（n）、插入节点O（1）、删除节点O（1）；

4、不适合快速的定位数据，适合动态的插入和删除数据的应用场景；

5、链表在内存中可以不连续，数组是连续的存储空间；

1、结构体实现

struct node{
    node(int data) : data(data), next(NULL){}
    int data;
    node *next;
};
// 输出1234四个数的链表
int main(){
    node *head = NULL;
    head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);

    node *p = head;
    while(p != NULL){
        cout<data;
        p = p->next;
    }
    cout< 
2、数组实现
 
int data[100];
int nxt[100];

void add(int ind, int p, int val){
    nxt[ind] = p;
    data[p] = val;
    return ;
}

int main() {
    int head = 3;
    data[3] = 0;
    add(3, 5, 1);
    add(5, 2, 2);
    add(2, 7, 3);
    add(7, 4, 4);
    int p = head;
    while(p != 0) {
        cout << data[p] << " ";
        p = nxt[p];
    }
    cout << endl;
    return 0;
}
 
三、应用场景 
1、 *** 作系统内的动态内存分配：将内存碎片通过链表关联起来；
 
2、LRU缓存淘汰算法；
 
！！！链表和数组的性能对比：
 
软件层面：链表是不连续的，便于扩充，数组是连续的，扩充比较麻烦；
 
硬件层间：数组可以进行CPU缓存优化，也就是读取时多读取一些数据，由于链表是随机存储的，无法进行CPU缓存优化；
 
四、LeetCode刷题 
141、环形链表 
题目：给定一个链表，判断链表中是否有环；
 
思考：
 
​ 在一开始能想到的方法就是暴力法，通过哈希表存储访问过的节点，如果插入节点被访问过，说明链表成环；（需要额外的存储空间）
 
最优解法：快慢指针
 
​ 设置两个指针，慢指针指向head节点，快指针指向head.next节点，慢指针一次走一步，快指针一次走两步，当两个指针相遇，证明有环；
 
C++实现（快慢指针思想）：
 
bool hasCycle(ListNode *head) {
    if(head == NULL) return false;
    ListNode *p = head, *q = head->next;
    while(p != q && q && q->next){
        p = p->next;
        q = q->next->next;
    }
    return p == q;
}
 
Python实现（快慢指针思想）：
 
def hasCycle(self, head: ListNode) -> bool:
    if not head: return False
    p, q = head, head.next
    while p!=q and q and q.next:
        p = p.next
        q = q.next.next        
	return p == q
 
142、环形链表Ⅱ 
题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL；
 
思考：
 
​ 这道题一开始想到的方法就是基于上面的快慢指针思想，但需要找到入环节点，需要通过画图找到对应关系，实际上这是一道数学题；
 
最优解法：
 
首先我们的能够得到的信息是快慢指针相遇处的节点位置；
 
第一步先思考慢指针走到入环节点处的情况，如下图：
 
 
由上图可知，p为慢指针，q为快指针；
 
当快慢指针相遇时，情况如下图：
 
 
此时p、q两个指针相遇，并且在距离入环节点x处，通过这个图我们不难看出，此时的节点再走a个距离就到入环结点，而头节点距离入环节点也是a个距离，那么定义一个指向头节点的指针就可以找到入环节点的位置；
 
C++实现：
 
ListNode *detectCycle(ListNode *head) {
    if(head == NULL) return NULL;
    ListNode *p = head, *q = head;
    while(q && q->next) {
        p = p->next;
        q = q->next->next;
        if(p == q){
            q = head;
            while(p != q){
            q = q->next;
            p = p->next;
            }
            return p;
		}
	}
	return NULL;
}
 
Python实现：
 
def detectCycle(self, head: ListNode) -> ListNode:
    if not head: return None
    p, q = head, head
    while q and q.next:
        p = p.next
        q = q.next.next
        if (p == q):
            q = head
            while(p != q):
                p = p.next
                q = q.next
			return p
	return None
 
202、快乐数 
题目：判断一个数是不是快乐数（每个位置的平方和，最终这个数变为1）；
 
思考：
 
​ 可以把快乐数计算的过程想成一个链表，当成环的时候或者等于1的时候停止，也就是还是用快慢指针的思想找环；
 
最优解法：
 
​ 这个题还是可以具象化成链表找环的问题，不同点在于每个节点的next对象需要自定义一个函数来生成，是环形链表的同类型问题；
 
C++实现：
 
int getNext(int x){
    int z = 0;
    while(x){
        z += (x%10)*(x%10);
        x /= 10;
	}
	return z;
}

bool isHappy(int n) {
    int p =n, q = n;
    do{
        p = getNext(p);
        q = getNext(getNext(q));
	}while(q != p && q != 1);
	return q == 1;
}
 
Python实现：
 
def isHappy(self, n: int) -> bool:
    def getNext(x):
        z = 0
        while x:
            x, a = divmod(x, 10)	# divmod函数实现返回除以10后的商和余数
            z += a ** 2
		return z
        
	p = n
	q = getNext(n)
    while(p != q and q != 1):
        p = getNext(p)
        q = getNext(getNext(q))
	return q == 1
 
206、反转链表 
题目：将给定的链表进行反转；
 
思考：
 
​ 首先想到的就是借助一个新的空节点，作为中间变量对链表进行反转，也就是三节点的 *** 作；
 
最优解法：
 
​ 使用中间变量是一种最笨的方法，增加了内存空间，我们可以通过递归的方式实现链表反转；
 
C++实现：
 
1、中间变量法
 
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode *pre = nullptr, *cur = head, *p = head->next;
    while(cur){
        cur->next = pre;
        pre = cur;
        (cur = p) && (p = p->next);     //这里用到一个短路逻辑
	}
	return pre;
}
 
2、递归
 
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode *tall = head->next, *p = reverseList(head->next);
    head->next = tall->next;
    tall->next = head;
    return p;
    }
 
Python实现（中间变量法）：
 
def reverseList(self, head: ListNode) -> ListNode:
    cur, pre = head, None
    while cur:
        tmp = cur.next
        cur.next= pre
        pre = cur
        cur = tmp
	return pre
 
92、反转链表Ⅱ 
题目：给定链表和区间，反转该区间；
 
思考：
 
​ 本质也是反转链表，只需找到区间，并且将区间左边当作头节点，重点注意边界设定；
 
最佳解法：
 
​ 将上题中的反转链表函数集成到该题，对函数进行一些修改，随后只需传入需要反转的左边节点以及反转的次数，即可实现链表的反转；
 
C++实现：
 
ListNode* reverseN(ListNode* head, int n) {
    if(n==1) return head;
    ListNode *tail = head->next, *p = reverseN(head->next, n - 1);
    head->next = tail->next;
    tail->next = head;
    return p;
}

ListNode* reverseBetween(ListNode* head, int m, int n) {
    // 创建一个哨兵节点指向头节点
    ListNode ret(0, head), *p = &ret;
    int cnt = n - m + 1;
    while(--m) p = p->next;
    p->next = reverseN(p->next, cnt);
    return ret.next;
}
 
Python实现：
 
def reverseN(self, head, k):
    pre, cur, tmp = None, head, None
    for _ in range(k):
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
	head.next = cur
	return pre
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
    tmp = ListNode()
    tmp.next = head
    pre = tmp
    for _ in range(left-1):
        pre = pre.next
	node = self.reverseN(pre.next, right-left+1)
    pre.next = node
    return tmp.next
 
25、K个一组翻转链表 
题目：给定链表和K值，按K个节点进行翻转，如果不够则不翻转；
 
思考：
 
​ 本质上没有发生变化，也是一个链表翻转的问题，并且是从头开始，我们只需要判断是否满足有K个节点的条件，实质是一个边界问题；
 
最佳解法：
 
​ 根据之前的代码进行改进，实现边界的判断；
 
C++实现：
 
ListNode* __reverseK(ListNode* head, int n) {
    if(n==1) return head;
    ListNode *tail = head->next, *p = __reverseK(head->next, n - 1);
    head->next = tail->next;
    tail->next = head;
    return p;
}

ListNode* reverseK(ListNode* head, int k) {
    ListNode *p = head;
    int cnt = k;
    while(--k && p) p = p->next;
    if(p == nullptr) return head;
    return __reverseK(head, cnt);
}

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode ret(0, head), *p = &ret, *q = p->next;
    while((p->next = reverseK(q, k)) != q){
        p = q;
        q = q->next;
    }
    return ret.next;
}
 
Python实现：
 
def reverse(self, head, k):
    pre = None
    cur = head
    tmp = None
    for _ in range(k):
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
	head.next = cur
	return pre
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
    empty = ListNode()
    empty.next = head
    pre = empty
    while True:
        q = pre
        for _ in range(k):
            if not q.next: return empty.next
            q = q.next
		node = self.reverse(pre.next, k)
		pre.next = node
		for _ in range(k):
			re = pre.next
	return empty.next
 
61、旋转链表 
题目：将一个链表旋转k次，每次向右旋转，k可大于链表长度；
 
思考：
 
​ 这道题我们可以想成头尾相连的一个环形链表，由于是顺时钟旋转的，所以需要从最后一个节点往前数，判断最终头节点的位置很关键；
 
最佳解法：
 
​ 我们通过遍历链表可以找到链表最后一个节点以及链表的长度，随后将链表成环；由于k会大于链表长度，我们通过取余 *** 作去掉无效旋转次数，通过长度减去k的值得到头节点位置并断开；
 
C++实现：
 
ListNode* rotateRight(ListNode* head, int k) {
    if (head == nullptr) return head;
    int n = 1;
    ListNode *p = head;
    while(p->next) p = p->next, n ++;
    p->next = head;
    k %= n, k = n - k;
    while(k--) p = p->next;
    head = p->next;
    p->next = nullptr;
    return head;    
 
Python实现就不在这说明了，逻辑与C++实现相同；
 
19、删除链表的倒数第N个节点 
题目：传入一个链表，删除倒数第N个节点，返回头节点（尽量用一趟扫描实现）；
 
思考：
 
​ 首先想法就是先遍历得到链表的长度，再通过长度减去N得到删除的节点，但这样就会扫描两次；
 
最佳解法：
 
​ 在判断环形链表中有快慢指针的思想，这里实际也是可以用双指针实现一次扫描删除节点。假设p指针先走N布，随后再一起走到尾部，q指针的位置就是删除节点的前一个节点；
 
 
（由于没有趁手画图工具，图片比较简陋。。。大家懂就好）
 
C++实现：
 
ListNode* removeNthFromEnd(ListNode* head, int n) {
    if(head->next == nullptr) return nullptr;
    ListNode ret(0, head), *q = &ret, *p = head;
    while(--n) p = p->next;
    while(p->next) p = p->next, q = q->next;
    q->next = q->next->next;
    return ret.next;
 
Python实现逻辑与C++相同，大家可自行实现，相信大家可以的！
 
83、删除排序链表中的重复元素 
题目：给定一个按升序排序的链表，删除重复元素，使每个元素只出现一次；
 
思考：
 
​ 这个题目想到的思想很简单，就是一直遍历下去，有重复的就删除该节点；
 
C++实现：
 
ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr) return nullptr;
    ListNode *p = head;
    while(p->next) {
        if (p->val == p->next->val) {
        	p->next = p->next->next;
        }else
            p = p->next;
        }
	return head;
}
 
82、删除排序链表中的重复元素Ⅱ 
题目：若出现重复元素，则将重复的元素个数变为0；
 
思考：
 
​ 该题和上一题的解题是相似的，但是需要一个哨兵节点指向头节点，需要注意的是我们要先判断p指针的后两个元素是否相同，再用指针q去找更多重复元素
 
C++代码：
 
ListNode* deleteDuplicates(ListNode* head) {
    ListNode ret(0, head), *p = &ret, *q;
    while(p->next){
        if (p->next->next && p->next->val == p->next->next->val){
            q = p->next->next;
            while(q && q->val == p->next->val)  q = q->next;
            p->next = q;
		}else{
			p = p->next;
		}
		}
	return ret.next;
}
 
24、两两交换链表中的节点 
题目：每两个节点交换一次，不足两个不进行交换；
 
这里就不放出思路了，大家可以自己尝试一下，下面是我的代码：
 
ListNode* swap(ListNode* head) {
    ListNode *cur = head, *p = head->next, *pre = nullptr;
    pre = p->next;
    p->next = cur;
    cur->next = pre;
    return p;
}
ListNode* swapPairs(ListNode* head) {
    if(head == nullptr || head->next == nullptr) return head;
    ListNode ret(0, head), *p = &ret;
    while(p->next && p->next->next){
        p->next = swap(p->next);
        p = p->next->next;
	}
	return ret.next;
}
 
五、总结 
本次的一些重要技巧：
 
 
快慢指针思想；
 
 
哨兵节点（指向头节点）；
 
 
递归思想在链表中的使用；
 
 
多画图进行思考，判断各种情况；
 
 
​ 我刷题的方式是看C++部分代码的思想，然后自己用Python进行复现，基本做完5道题后，后面的题目就可以自己写出来了，这是我个人的学习方式，仅供参考，欢迎一起刷题的小伙伴来互相交流；
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/4752278.html