剑指OFFER练习记录(三. 链表)

这是自己刷题的笔记, 有Java和Python的实现, 尽量每一题都挑选典型的方法进行记录. 题目的分类是按照牛客平台分类的.

从尾到头打印链表

题目:
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思路:
可以用栈来存储每一个节点的数据, 遍历完链表后取出打印.或者对链表进行翻转, 到尾部时翻转回来并打印

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {

        Stack<Integer> help = new Stack<>();
        ArrayList<Integer> res = new ArrayList<>();

        while (listNode != null){
            help.add(listNode.val);
            listNode = listNode.next;
        }
        while (!help.isEmpty()){
            res.add(help.pop());
        }

        return res;
    }
}

翻转链表

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode) -> list:
        res = []
        if listNode is None:
            return res

        pre = None
        while listNode is not None:
            nxt = listNode.next
            listNode.next = pre
            pre = listNode
            listNode = nxt


        listNode = pre
        pre = None
        while listNode is not None:
            res.append(listNode.val)
            nxt = listNode.next
            listNode.next = pre
            pre = listNode
            listNode = nxt
        
        return res

入口环结点

题目:
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路:
可以利用哈希表记录沿途的节点值, 遍历链表, 如果哈希表中有该值表是环的入口结点
或者
利用快慢指针遍历链表

• 快指针走两步, 慢指针走一步
• 当快慢指针相遇时, 快指针回到链表的头部
• 继续遍历, 当快慢指针相遇时, 此时指针指向的就是入口结点

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null || pHead.next.next == null) {
            return null;
        }

        ListNode n1 = pHead.next;
        ListNode n2 = pHead.next.next;

        while (n1 != n2) {
            // 如果快指针指向了空结点, 或者无环链表的最后一个结点, 此时链表无环
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }


        n2 = pHead;
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;

    }
}

利用哈希集合记录结点是否已经出现

class Solution:
    def EntryNodeOfLoop(self, pHead):
        node_set = set()
        while pHead is not None:
            if pHead.val in node_set:
                return pHead
            node_set.add(pHead.val)
            pHead = pHead.next

        return None

排序链表删除重复结点

题目:
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路:
设置一个递归函数, 传入的参数是链表的头部, 返回值是链表的结点, 这个结点的特点是它与下一个结点不重复. 也就是说是第一个不重复的结点.

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) { // 只有0个或1个结点，则返回
            return pHead;
        }

        if (pHead.val == pHead.next.val) { // 当前结点是重复结点
            ListNode pNode = pHead.next;
            while (pNode != null && pNode.val == pHead.val) {
                // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
                pNode = pNode.next;
            }
            return deleteDuplication(pNode); // 从第一个与当前结点不同的结点开始递归
        } else { // 当前结点不是重复结点
            pHead.next = deleteDuplication(pHead.next); // 保留当前结点，从下一个结点开始递归, 并将其接到当前结点的后边
            return pHead;
        }
    }
}

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead is None or pHead.next is None:
            return pHead

        if pHead.val == pHead.next.val:
            pNode = pHead.next
            while pNode is not None and pHead.val == pNode.val:
                pNode = pNode.next
            # 找到这个不重复的结点后, 重新进行递归操作
            return self.deleteDuplication(pNode)
        else:
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead