《剑指Offer》链表全题——妙解思路，难度由浅入深

灰太狼 2023-09-28 21:01 24阅读 0赞

**目录**

JZ6 从尾到头打印链表

JZ24 反转链表

JZ25 合并两个排序的链表

JZ52 两个链表的第一个公共结点

JZ23 链表中环的入口结点

JZ22 链表中倒数最后k个结点

JZ35 复杂链表的复制

JZ76 删除链表中重复的结点

--------------------

# JZ6 从尾到头打印链表 #

> 思路：建立一个顺序表，用一个指针遍历链表并每次插入在顺序表的0位置处，最后得到的就是逆序。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            //可以设置每次从顺序表的0下标位置插入，得到的就是逆序
            ArrayList<Integer> list = new ArrayList<>();
            ListNode cur = listNode;
            while(cur != null){
                list.add(0,cur.val);
                cur = cur.next;
            }
            return list;
        }

--------------------

# JZ24 反转链表 #

> 解法一（辅助栈）：建立一个辅助栈，将链表元素全部入栈，最后在一个一个出栈并从到尾修改链表值

public ListNode ReverseList(ListNode head) {
            //通过辅助栈来反转
            Stack<Integer> stack = new Stack<>();
            ListNode cur = head;
            //入栈
            while(cur != null){
                stack.push(cur.val);
                cur = cur.next;
            }
            //出栈进入链表
            cur = head;
            while(!stack.isEmpty()){
                cur.val = stack.pop();
                cur = cur.next;
            }
            return head; 
        }

> 解法二思路（新链表头插法）：建立一个新链表，遍历需要反转的链表，同时每次头插新链表即可

public ListNode ReverseList(ListNode head) {
            ListNode list = null;
            ListNode listHead = null;
            ListNode cur = head;
            //每次头插
            while(cur != null){
                if(listHead == null){
                    list = new ListNode(cur.val);
                    listHead = list;
                }else{
                    listHead = new ListNode(cur.val);
                    listHead.next = list;
                    list = listHead;
                }
                cur = cur.next;
            }
            return listHead;
        }

--------------------

# JZ25 合并两个排序的链表 #

> 解法一思路（不够优化，易理解）：创建一个新链表，用两个指针遍历要合并的两个链表，两链表结点值谁小，谁就尾插如新链表中，往复以上操作，最后返回新链表头节点即可。

public ListNode Merge(ListNode list1,ListNode list2) {
            //严防有一方为空
            if(list1 == null){
                return list2;
            }
            if(list2 == null){
                return list1;
            }
            ListNode start1 = list1;
            ListNode start2 = list2;
            ListNode head = null;
            ListNode cur = null;
            ListNode pd = null;
            //有一方为空就停下来
            while(start1 != null && start2 != null){
                if(start1.val < start2.val){
                    if(head == null){
                        head = new ListNode(start1.val);
                        cur = head;
                        pd = head;
                    }else{
                        cur = new ListNode(start1.val);
                        pd.next = cur;
                        pd = cur;
                    }
                    start1 = start1.next;
                }else{
                    if(head == null){
                        head = new ListNode(start2.val);
                        cur = head;
                        pd = head;
                    }else{
                        cur = new ListNode(start2.val);
                        pd.next = cur;
                        pd = cur;
                    }
                    start2 = start2.next;
                }
            }
            //检测还有哪一方没有完
            if(start1 != null){
                cur.next = start1;
            }
            if(start2 != null){
                cur.next = start2;
            }
            return head;
        }

> 解法二思路（虚拟链表，优化时间复杂度为O(1)）:创建一个虚拟的头节点，比较待合并的两链表的结点值大小，虚拟新结点的下一个next就是他，往复以上操作（相当于不断在待合并的两链表之间建立联系），最后返回虚拟头结点的next即可。

public ListNode Merge(ListNode list1,ListNode list2) {
            //优化空间复杂度为O(1)
            ListNode head = new ListNode(-1);//虚拟结点
            ListNode cur = head;
            while(list1 != null && list2 != null){
                if(list1.val < list2.val){
                    cur.next = list1;
                    cur = list1;
                    list1 = list1.next;
                }else{
                    cur.next = list2;
                    cur = list2;
                    list2 = list2.next;
                }
            }
            if(list1 != null){
                cur.next = list1;
            }
            if(list2 != null){
                cur.next = list2;
            }
            return head.next;
        }

--------------------

# JZ52 两个链表的第一个公共结点 #

> 思路：先分别遍历两个链表求出各自长度，再比较大小求出差值，让链表较长的一方先走完差值，两链表就可以同步往后走，找到公共结点，若有一方为空，则说明没有公共结点。

public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
            if(head1 == null && head2 == null){
                return null;
            }
            ListNode cur1 = head1;
            ListNode cur2 = head2;
            int count1 = 0;
            int count2 = 0;
            //先求出链表的长度差
            while(cur1 != null){
                count1++;
                cur1 = cur1.next;
            }
            while(cur2 != null){
                count2++;
                cur2 = cur2.next;
            }
            //比较大小，谁长谁就先走长度的差值,使其同步
            cur1 = head1;
            cur2 = head2;
            if(count1 > count2){
                int D_value = count1 - count2;
                while(D_value > 0){
                    D_value--;
                    cur1 = cur1.next;
                }
            }else{
                int D_value = count2 - count1;
                while(D_value > 0){
                    D_value--;
                    cur2 = cur2.next;
                }
            }
            //同步后两个一起走,相遇后停下,cur1 == null是防止对null解引用，并且说明没有公共结点
            while(cur1 != null && cur1.val != cur2.val){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            //若为空说明没有公共点
            if(cur1 == null){
                return null;
            }else{
                return cur1;
            }
        }

--------------------

# JZ23 链表中环的入口结点 #

> 解法一（哈希法）：创建一个哈希表来来记录用cur指针遍历的每一个元素，一旦发现重复，立刻return。

public ListNode EntryNodeOfLoop(ListNode pHead) {
            Set<Integer> set = new HashSet();
            ListNode cur = pHead;
            while(cur != null){
                //一旦发现重复，立刻返回
                if(set.contains(cur.val)){
                    return cur;
                }
                set.add(cur.val);
                cur = cur.next;
            }
            return null;
        }

> 解法二（快慢指针+数学推理）,博主已经整理出文章，快来看看吧~
> 
> [http://t.csdn.cn/x9E1w][http_t.csdn.cn_x9E1w]

--------------------

# JZ22 链表中倒数最后k个结点 #

此题给出了进阶要求：时间复杂度 O(n)，空间复杂度O(1)；

以下两种方法皆符合

> 解法一（差值法）：通过cur指针遍历链表计算出长度，再计算与K的差值，若差值小于0，则返回null；否则重置cur，让cur走差值步即可，
> 
> 最后返回cur；

public ListNode FindKthToTail (ListNode pHead, int k) {
            int count = 0;
            ListNode cur = pHead;
            //计数
            while(cur != null){
                count++;
                cur = cur.next;
            }
            cur = pHead;
            //求差值,确定走的步数
            int D_value = count - k;
            if(D_value < 0){
                return null;
            }
            while(D_value > 0){
                D_value--;
                cur = cur.next;
            }
            return cur;
        }

> 解法二（快慢指针法）:让快指针先走K步，然后快慢指针一起走，直到fast为空时返回慢指针，注意K值大于链表的情况。

public ListNode FindKthToTail (ListNode pHead, int k) {
            ListNode fast = pHead;
            ListNode slow = pHead;
            //快指针先走k步
            while(k > 0 && fast != null){
                k--;
                fast = fast.next;
            }
            //严防K值大于链表长度
            if(k > 0 && fast == null){
                return null;
            }
            //快慢指针一起走,fast为空时，返回即可
            while(fast != null){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }

--------------------

# JZ35 复杂链表的复制 #

> 思路（HashMap法）：注意此题需要进行深拷贝，先用虚拟头节点尾插复制一份原链表的val，同时将待复制和复制的结点地址同时存入HashMap中(key为待复制结点的地址，val为复制的结点的地址)，最后通过HashMap其中的对应关系即可深拷贝Random指针，此题用画图理解会更加容易，此题也是百度的面试题，博主已经整理出了画图理解的思路，快来看看吧！
> 
> [http://t.csdn.cn/FGVly][http_t.csdn.cn_FGVly]

public RandomListNode Clone(RandomListNode pHead) {
            //通过HashMap来确定随机指针
            Map<RandomListNode, RandomListNode> map = new HashMap<>();
            //虚拟头结点
            RandomListNode head = new RandomListNode(-1);
            RandomListNode cur = head;
            //拷贝val值，并创建新链表
            RandomListNode pCur = pHead;
            while(pCur != null){
                cur.next = new RandomListNode(pCur.label);
                cur = cur.next;
                map.put(pCur, cur);
                pCur = pCur.next;
            }
            cur = head.next;
            pCur = pHead;
            //随机指针的复制
            while(pCur != null){
                cur.random = map.get(pCur.random);
                pCur = pCur.next;
                cur = cur.next;
            }
            return head.next;
        }

--------------------

# JZ76 删除链表中重复的结点 #

> 写法一（三指针法，不够优化，但便于理解）：此题与普通的删除链表中重复的结点不同，一旦重复，则全部删除；
> 
> 可以先创建一个虚拟结点，这个虚拟结点是为了方便三个指针分别位于前中后以及避免\{1,1\}情况，造成空指针异常，接着让这三个指针遍历链表，一旦发现前指针和中指针重复，就让前指针继续走下去，直到值不同，停下来，若为空，将后指针的next置为空返回头指针即可，若不为空，将后指针的next指向他，继续向后调整即可(如下图)：

![3804376a5c6e472484af5779172470fb.gif][]

public ListNode deleteDuplication(ListNode pHead) {
            if(pHead == null){
                return null;
            }
            //创建一个虚拟头节点
            ListNode head = new ListNode(-1);
            head.next = pHead;
            ListNode cur = pHead;
            ListNode prev = head;
            ListNode prevPrev = null;
            while(cur != null){
                //找到了
                if(prev.val == cur.val){
                    //继续找有没有重复的
                    while(cur != null && prev.val == cur.val){
                        cur = cur.next;
                    }
                    if(cur == null){
                        prevPrev.next = null;
                        return head.next;
                    }else{
                        prevPrev.next = cur;
                        prev = cur;
                        cur = cur.next;
                    }
                }else{
                    prevPrev = prev;
                    prev = cur;
                    cur = cur.next;
                }
            }
            return head.next;
        }

> 写法二（单个指针）：与思路一的思想是相同的，不易看懂，但是更优化

public ListNode deleteDuplication(ListNode pHead) {
            if(pHead == null){
                return null;
            }
            //创建一个虚拟头节点
            ListNode head = new ListNode(-1);
            head.next = pHead;
            ListNode cur = head;
            while(cur.next != null && cur.next.next != null){
                //发现重复
                if(cur.next.val == cur.next.next.val){
                    int tmp = cur.next.val;
                    //继续向后找出所有相同的，注意while条件的先后顺序不能变
                    while(cur.next != null && cur.next.val == tmp){
                        cur.next = cur.next.next;
                    }
                }else{
                    cur = cur.next;
                }
            }
            return head.next;
        }

--------------------

![ff4a67a871e245a5b9fb829cecf5f6d4.gif][]

[http_t.csdn.cn_x9E1w]: http://t.csdn.cn/x9E1w
[http_t.csdn.cn_FGVly]: http://t.csdn.cn/FGVly
[3804376a5c6e472484af5779172470fb.gif]: https://img-blog.csdnimg.cn/3804376a5c6e472484af5779172470fb.gif
[ff4a67a871e245a5b9fb829cecf5f6d4.gif]: https://img-blog.csdnimg.cn/ff4a67a871e245a5b9fb829cecf5f6d4.gif