大家好,我是bug郭,一名双非科班的在校大学生。对C/JAVA、数据结构、Spring系列框架、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN java领域新星创作者blog.csdn.net/bug…
• 掘金LV3用户 juejin.cn/user/bug…
• 阿里云社区专家博主,星级博主,developer.aliyun.com/bug…
• 华为云云享专家 bbs.huaweicloud.com/bug…

链表中倒数最后k个结点

题目链接: 链表中倒数最后k个结点

题目分析:

• 遍历拿到数组长度,再次遍历size-k返回即可!
• 我们可以通过双指针,让fast先走k个节点,slow指针再开始出发,当fast走完,slow就到了倒数第k个节点位置!

 public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        int size = 0;
        ListNode cur = pHead;
        while(cur!=null){
            cur = cur.next;
            size++;
        }
        if(size<k){
            return null;
        }
        int n = size - k;
        while(n-->0){
            pHead = pHead.next;
        }
        return pHead;
    }
}

python

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        # 判断是否有倒数第k个节点!
        size = 0
        cur = pHead
        while cur:
            size +=1
            cur = cur.next
        #不存在倒数第k个节点!
        if size <k:
            return None
        # 遍历!
        n = size -k
        cur = pHead
        while n:
            cur = cur.next
            n -=1
        return cur

双指针
java

 public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode slow = pHead,fast = pHead;
        while(k-->0){
            if(fast ==null)
                return null;
            fast = fast.next;
        }
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

python

def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        # write code here
        fast = slow = pHead
        while k:
            if fast == None:
                return None
            fast = fast.next
            k-=1
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

复杂链表的复制

题目链接:复杂链表的复制

题目分析:

• 这里需要浅拷贝,我们可以遍历整个链表通过哈希表保存当前节点和random的映射关系,就是复制好所有的random节点,由此也就复制了所有链表的节点,然后我们需要做的就是再次遍历链表,然后把链表的连接连上即可!
  

java

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null) return null;
        //保存节点和random节点的映射关系!
        //并且先创建部分链表,除了随机指针!
        Map<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        while(cur!=null){
            map.put(cur,new RandomListNode(cur.label));
            cur = cur.next; 
        }
        //复制!
        cur = pHead;
        while(cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }
}

python

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        cur = pHead
        table = {}
        if pHead == None:
            return None
        # 获取映射关系
        while cur:
            table[cur] = RandomListNode(cur.label)
            cur = cur.next
        #进行连接!
        cur = pHead
        while cur:
            table[cur].next = table.get(cur.next)
            table[cur].random = table.get(cur.random)
            cur = cur.next
        return table[pHead]