• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

[BAT面试必备] ——几道常见的链表算法题

技术杂谈 勤劳的小蚂蚁 4个月前 (02-01) 95次浏览 已收录 0个评论 扫描二维码

1. 两数相加

题目描述

Leetcode:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
  1. 输入:(2->4->3)+(5->6->4)
  2. 输出:7->0->8
  3. 原因:342+465=807

问题分析

Leetcode官方详细解答地址:
要对头结点进行操作时,考虑创建哑节点dummy,使用dummy->next表示真正的头节点。这样可以避免处理头节点为空的边界问题。
我们使用变量来跟踪进位,并从包含最低有效位的表头开始模拟逐 位相加的过程。

Solution

我们首先从最低有效位也就是列表 l1和 l2 的表头开始相加。注意需要考虑到进位的情况!
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. //https://leetcode-cn.com/problems/add-two-numbers/description/
  10. classSolution{
  11. publicListNode addTwoNumbers(ListNode l1,ListNode l2){
  12.    ListNode dummyHead =newListNode(0);
  13.    ListNode p = l1, q = l2, curr = dummyHead;
  14.    //carry 表示进位数
  15.    int carry =0;
  16.    while(p !=null|| q !=null){
  17.        int x =(p !=null)? p.val :0;
  18.        int y =(q !=null)? q.val :0;
  19.        int sum = carry + x + y;
  20.        //进位数
  21.        carry = sum /10;
  22.        //新节点的数值为sum % 10
  23.        curr.next =newListNode(sum %10);
  24.        curr = curr.next;
  25.        if(p !=null) p = p.next;
  26.        if(q !=null) q = q.next;
  27.    }
  28.    if(carry >0){
  29.        curr.next =newListNode(carry);
  30.    }
  31.    return dummyHead.next;
  32. }
  33. }

2. 翻转链表

题目描述

剑指 offer:输入一个链表,反转链表后,输出链表的所有元素。

问题分析

这道算法题,说直白点就是:如何让后一个节点指向前一个节点!在下面的代码中定义了一个 next 节点,该节点主要是保存要反转到头的那个节点,防止链表 “断裂”。

Solution

  1. publicclassListNode{
  2.    int val;
  3.    ListNode next =null;
  4.    ListNode(int val){
  5.        this.val = val;
  6.    }
  7. }
  1. /**
  2. *
  3. * @author Snailclimb
  4. * @date 2018年9月19日
  5. * @Description: TODO
  6. */
  7. publicclassSolution{
  8.    publicListNodeReverseList(ListNode head){
  9.        ListNode next =null;
  10.        ListNode pre =null;
  11.        while(head !=null){
  12.            // 保存要反转到头的那个节点
  13.            next = head.next;
  14.            // 要反转的那个节点指向已经反转的上一个节点(备注:第一次反转的时候会指向null)
  15.            head.next = pre;
  16.            // 上一个已经反转到头部的节点
  17.            pre = head;
  18.            // 一直向链表尾走
  19.            head = next;
  20.        }
  21.        return pre;
  22.    }
  23. }
测试方法:
  1.    publicstaticvoid main(String[] args){
  2.        ListNode a =newListNode(1);
  3.        ListNode b =newListNode(2);
  4.        ListNode c =newListNode(3);
  5.        ListNode d =newListNode(4);
  6.        ListNode e =newListNode(5);
  7.        a.next = b;
  8.        b.next = c;
  9.        c.next = d;
  10.        d.next = e;
  11.        newSolution().ReverseList(a);
  12.        while(e !=null){
  13.            System.out.println(e.val);
  14.            e = e.next;
  15.        }
  16.    }
输出:
  1. 5
  2. 4
  3. 3
  4. 2
  5. 1

3. 链表中倒数第k个节点

题目描述

剑指offer: 输入一个链表,输出该链表中倒数第k个结点。

问题分析

链表中倒数第k个节点也就是正数第(L-K+1)个节点,知道了只一点,这一题基本就没问题!
首先两个节点/指针,一个节点 node1 先开始跑,指针 node1 跑到 k-1 个节点后,另一个节点 node2 开始跑,当 node1 跑到最后时,node2 所指的节点就是倒数第k个节点。

Solution

  1. /*
  2. public class ListNode {
  3.    int val;
  4.    ListNode next = null;
  5.    ListNode(int val) {
  6.        this.val = val;
  7.    }
  8. }*/
  9. // 时间复杂度O(n),一次遍历即可
  10. // https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
  11. publicclassSolution{
  12.    publicListNodeFindKthToTail(ListNode head,int k){
  13.        // 如果链表为空或者k小于等于0
  14.        if(head ==null|| k <=0){
  15.            returnnull;
  16.        }
  17.        // 声明两个指向头结点的节点
  18.        ListNode node1 = head, node2 = head;
  19.        // 记录节点的个数
  20.        int count =0;
  21.        // 记录k值,后面要使用
  22.        int index = k;
  23.        // p指针先跑,并且记录节点数,当node1节点跑了k-1个节点后,node2节点开始跑,
  24.        // 当node1节点跑到最后时,node2节点所指的节点就是倒数第k个节点
  25.        while(node1 !=null){
  26.            node1 = node1.next;
  27.            count++;
  28.            if(k <1&& node1 !=null){
  29.                node2 = node2.next;
  30.            }
  31.            k--;
  32.        }
  33.        // 如果节点个数小于所求的倒数第k个节点,则返回空
  34.        if(count < index)
  35.            returnnull;
  36.        return node2;
  37.    }
  38. }

4. 删除链表的倒数第N个节点

Leetcode:给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
  1. 给定一个链表:1->2->3->4->5, n =2.
  2. 当删除了倒数第二个节点后,链表变为1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
该题在 leetcode 上有详细解答,具体可参考 Leetcode.

问题分析

我们注意到这个问题可以容易地简化成另一个问题:删除从列表开头数起的第 (L – n + 1)个结点,其中 L是列表的长度。只要我们找到列表的长度 L,这个问题就很容易解决。

Solution

两次遍历法
首先我们将添加一个 哑结点 作为辅助,该结点位于列表头部。哑结点用来简化某些极端情况,例如列表中只含有一个结点,或需要删除列表的头部。在第一次遍历中,我们找出列表的长度 L。然后设置一个指向哑结点的指针,并移动它遍历列表,直至它到达第 (L – n) 个结点那里。我们把第 (L – n)个结点的 next 指针重新链接至第 (L – n + 2)个结点,完成这个算法
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. // https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/description/
  10. publicclassSolution{
  11.    publicListNode removeNthFromEnd(ListNode head,int n){
  12.        // 哑结点,哑结点用来简化某些极端情况,例如列表中只含有一个结点,或需要删除列表的头部
  13.        ListNode dummy =newListNode(0);
  14.        // 哑结点指向头结点
  15.        dummy.next = head;
  16.        // 保存链表长度
  17.        int length =0;
  18.        ListNode len = head;
  19.        while(len !=null){
  20.            length++;
  21.            len = len.next;
  22.        }
  23.        length = length - n;
  24.        ListNode target = dummy;
  25.        // 找到 L-n 位置的节点
  26.        while(length >0){
  27.            target = target.next;
  28.            length--;
  29.        }
  30.        // 把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点
  31.        target.next = target.next.next;
  32.        return dummy.next;
  33.    }
  34. }
复杂度分析:
  • 时间复杂度 O(L) :该算法对列表进行了两次遍历,首先计算了列表的长度 LL 其次找到第 (L – n)(L−n) 个结点。 操作执行了 2L-n2L−n 步,时间复杂度为 O(L)O(L)。
  • 空间复杂度 O(1) :我们只用了常量级的额外空间。
进阶——一次遍历法:
链表中倒数第N个节点也就是正数第(L-N+1)个节点。
其实这种方法就和我们上面第四题找“链表中倒数第k个节点”所用的思想是一样的。基本思路就是: 定义两个节点 node1、node2;node1 节点先跑,node1节点 跑到第 n 个节点的时候,node2 节点开始跑。当node1 节点跑到最后一个节点时,node2 节点所在的位置就是第 (L-n ) 个节点(L代表总链表长度,也就是倒数第 n+1 个节点)
  1. /**
  2. * Definition for singly-linked list.
  3. * public class ListNode {
  4. *     int val;
  5. *     ListNode next;
  6. *     ListNode(int x) { val = x; }
  7. * }
  8. */
  9. publicclassSolution{
  10.    publicListNode removeNthFromEnd(ListNode head,int n){
  11.        ListNode dummy =newListNode(0);
  12.        dummy.next = head;
  13.        // 声明两个指向头结点的节点
  14.        ListNode node1 = dummy, node2 = dummy;
  15.        // node1 节点先跑,node1节点 跑到第 n 个节点的时候,node2 节点开始跑
  16.        // 当node1 节点跑到最后一个节点时,node2 节点所在的位置就是第 (L-n ) 个节点,也就是倒数第 n+1(L代表总链表长度)
  17.        while(node1 !=null){
  18.            node1 = node1.next;
  19.            if(n <1&& node1 !=null){
  20.                node2 = node2.next;
  21.            }
  22.            n--;
  23.        }
  24.        node2.next = node2.next.next;
  25.        return dummy.next;
  26.    }
  27. }

5. 合并两个排序的链表

题目描述

剑指offer:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

问题分析

我们可以这样分析:
  1. 假设我们有两个链表 A,B;
  2. A的头节点A1的值与B的头结点B1的值比较,假设A1小,则A1为头节点;
  3. A2再和B1比较,假设B1小,则,A1指向B1;
  4. A2再和B2比较 就这样循环往复就行了,应该还算好理解。
考虑通过递归的方式实现!

Solution

递归版本:
  1. /*
  2. public class ListNode {
  3.    int val;
  4.    ListNode next = null;
  5.    ListNode(int val) {
  6.        this.val = val;
  7.    }
  8. }*/
  9. //https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&tqId=11169&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
  10. publicclassSolution{
  11. publicListNodeMerge(ListNode list1,ListNode list2){
  12.       if(list1 ==null){
  13.           return list2;
  14.       }
  15.       if(list2 ==null){
  16.           return list1;
  17.       }
  18.       if(list1.val <= list2.val){
  19.           list1.next =Merge(list1.next, list2);
  20.           return list1;
  21.       }else{
  22.           list2.next =Merge(list1, list2.next);
  23.           return list2;
  24.       }      
  25.   }
  26. }
 

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:[BAT面试必备] ——几道常见的链表算法题
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00