剑指offer题解—链表

【牛客】从尾到头打印链表

题目描述

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

input:  1->2->3
output: 3,2,1

思路

1. 利用ArrayList的add()函数

  1. 非递归:ArrayList的add函数可以指定插入的位置,只要遍历链表的时候总是把当前节点的值放到0位置即可
ArrayList arrayList = new ArrayList<>();
public ArrayList printListFromTailToHead(ListNode listNode) {
        if (listNode == null) return arrayList;
        while(listNode != null){
            arrayList.add(0,listNode.val);
            listNode = listNode.next;
        }
        return arrayList;
    }
  1. 递归
ArrayList arrayList = new ArrayList<>();
public ArrayList printListFromTailToHead(ListNode listNode) {
        if (listNode == null) return arrayList;

        if(listNode != null){
            arrayList.add(0,listNode.val);
            printListFromTailToHead(listNode.next);
        }
        return arrayList;
    }

2. 递归

递归的思路和上面头插法的递归有点像,要逆序1->2->3,需要先逆序2->3,

public ArrayList printListFromTailToHead(ListNode listNode) {
        ArrayList arrayList = new ArrayList<>();
        if (listNode != null){
            arrayList.addAll(printListFromTailToHead(listNode.next));
            arrayList.add(listNode.val);
        }
        return arrayList;

    }

3. 头插法

头插法顾名思义是将节点插入到头部:在遍历原始链表时,将当前节点插入新链表的头部,使其成为第一个节点

利用头插法构建一个逆序链表,最后遍历逆序链表即可。我们需要一个不存值的头节点来方便进行插入操作。

头插法逆序链表的流程如下:

  1. 用一个节点存当前节点的下一个节点;
  2. 当前节点的下一个节点指向头节点的下一个节点
  3. 头节点的下一个节点指向当前节点
  4. 移动当前节点至下一个节点
  5. 循环1~4
public ArrayList printListFromTailToHead(ListNode listNode) {

        ListNode head = new ListNode(-1);

        while(listNode != null){
            ListNode next = listNode.next;
            listNode.next = head.next;
            head.next = listNode;
            listNode = next;
        }

       ArrayList res = new ArrayList();
       head = head.next;
       while(head != null){
           res.add(head.val);
           head = head.next;
       }
        return res;
    }

4. 栈

栈具有先进后出的特点,遍历一遍链表入栈,再出栈就可以得到逆序后的结果。

public ArrayList printListFromTailToHead(ListNode listNode) {
Stack stack = new Stack<>();
        while(listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList res = new ArrayList<>();
        while(!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }

【牛客】链表中环的入口节点

题目描述

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

思路

  1. 使用双指针,slow指针每次移动一个节点,fast指针每次移动两个节点,如果链表有环则slow和fast指针必定会相遇到环中的某个节点。

  2. 两个指针相遇后,让快指针从头开始走,慢指针从相遇点开始走,每次都是走一个节点,那么N圈之后,他们就会在入口节点相遇。

以上两个结论的证明见博客

 public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null) return null;
       ListNode slow = pHead;
       ListNode fast = pHead;

       while(fast != null && fast.next != null){
           fast = fast.next.next;
           slow = slow.next;

           if(fast == slow)
               break;
       }
       if(fast == null || fast.next == null)
           return null;
       slow = pHead;
       while(fast != slow){
           fast = fast.next;
           slow = slow.next;
       }
        return fast;
    }

【牛客】删除链表中的重复节点

题目描述

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

解题思路

因为链表是排好序的,所以相同的数字肯定在一块,遍历节点时检查当前节点与下一个节点是否相等

  1. 相等,循环跳过所有相等节点,因为函数求的就是所有不相等的节点,所有可以直接返回下一个不相同的节点。
  2. 直接指向下一个不相同的节点
public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null || pHead.next == null) return pHead;
        ListNode next = pHead.next;
        if(pHead.val == next.val){
            while( next != null && next.val == pHead.val ){
                next = next.next;
            }
            return deleteDuplication(next);
        }
        else{
            pHead.next = deleteDuplication(next);
            return pHead;
        }
    }

参考博客

  1. https://cyc2018.github.io/CS-Notes/#/notes/18.2%20%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E4%B8%AD%E9%87%8D%E5%A4%8D%E7%9A%84%E7%BB%93%E7%82%B9
  2. https://cyc2018.github.io/CS-Notes/#/notes/23.%20%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%8E%AF%E7%9A%84%E5%85%A5%E5%8F%A3%E7%BB%93%E7%82%B9
  3. https://cyc2018.github.io/CS-Notes/#/notes/6.%20%E4%BB%8E%E5%B0%BE%E5%88%B0%E5%A4%B4%E6%89%93%E5%8D%B0%E9%93%BE%E8%A1%A8
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复