印象博客印象博客

链表算法题练习

打印两个有序链表的公共部分

题目: 给定两个有序链表的头指针head1和head2,打印两个链表的公共部分。

【解答】

  • 因为是有序链表,直接从两个链表头部开始判断。如果 head1 小于 head2。则移动head1
  • 如果 head1 大于 head2。则移动head2。反之相等,则打印这个值,然后同时移动head1和head2

【代码如下】

public class NodeTest01 {


    public static class Node{
        int val;
        Node next;
        Node(int x) {
            this.val = x;
        }

    }

    public static void main(String[] args) {
        Node node1=new Node(1);
        node1.next=new Node(2);
        node1.next.next=new Node(3);
        node1.next.next.next=null;

        Node node2=new Node(1);
        node2.next=new Node(2);
        node2.next.next=new Node(6);
        node2.next.next.next=null;

        PrintCommonPart(node1,node2);
    }

    /**
     * 因为是有序 遍历判断相等 打印即可
     * @param node1
     * @param node2
     */
    public  static  void PrintCommonPart(Node node1,Node node2){
            while (node1!=null  &&  node2!=null){
                    if(node1.val< node2.val){
                        node1=node1.next;
                    }else if(node1.val> node2.val){
                         node2=node2.next;

                    }else {
                        System.out.println(node1.val);
                        node1=node1.next;
                        node2=node2.next;
                    }
            }


    }
}

删除单链表中倒数第K个节点

题目:实现一个函数,删除单链表中倒数第k个结点。
如果链表长度为N,时间浮躁度达到O(N),额外空间复杂度达到O(1)。

【案列】

  • 比如 链表 1>2>3 K=3 删除倒数第3个节点 也就是1 返回 2>3
  • 链表 1>2>3 K=4 删除倒数第4个节点 没有 直接返回原链表

【解答】

  • 如果链表为空或者K值小于1 这种情况下参数是无效的,直接返回即可。 除此之外,让链表从头总到尾,每移动一步就让指定的K值减1
  • 如果K值大于0 说明不用调整链表 因为链表根本没有倒数第K个节点,此时将原链表返回即可
  • 如果K值等于0 说明链表倒数第K个节点就是头节点,此时直接返回head.next即可
  • 如果K值小于0如何处理?如1>2>3,要删除节点2,则需要找到节点1.然后把节点1执行节点3即可,以此达到删除节点2的目的
  • 如何找到要删除节点前一个节点? 1: 重新从头节点开始,没移动1步就让K值加1。2 当K等于0时,移动停止,移动到的节点就是要删除节点的钱一个节点
  • 因为如果链表长度为N 要删除倒数第K个节点,很明显。倒数第K个节点的前一个节点就是第N-K个节点
  • 第一次遍历后,K的值变为K-N。第二次遍历时K值不断加1,加到0停止遍历,第二次遍历当然会停到N-K

【代码如下】

public static class Node{
        int val;
        Node next;
        Node(int x) {
            this.val = x;
        }
    }

public static Node removeLastKthNode(Node head, int lastKth) {
        if(head==null || lastKth<1){
            return head;
        }
        Node cur=head;
        while (cur!=null){
            lastKth--;
            cur=cur.next;
        }

        if(lastKth==0){
           head=head.next;
        }
        if(lastKth<0){
            cur=head;
            while (++lastKth !=0){
                cur=cur.next;
            }
            //改变删除节点的前一个节点的next指向
            cur.next=cur.next.next;
        }

        return head;
    }
public static void main(String[] args) {
        Node head=new Node(1);
        head.next=new Node(2);
        head.next.next=new Node(3);
        head.next.next.next=null;

        Node root=removeLastKthNode(head,3);
        while (root!=null){
            System.out.println(root.val);
            root=root.next;
        }
        // 输出 :2>3
    }

删除链表的中间节点

给定链表的头节点head,整数a和整数b,实现删除位于(a/b)处节点的函数。

【案列】

  • 1->2, 删除节点1
  • 1->2->3, 删除节点2
  • 1->2->3->4, 删除节点2
  • 1->2->3->4->5, 删除节点3

【解答】

  • 如果链表长度为空或1则不需要调整直接返回
  • 如果链表长度为2 则将头节点删除
  • 长度为3 删除第2个, 长度为四,删除第二个;长度为5 删除第三个,
  • 也就是链表长度每增加2 要删除的节点就后移动一个节点。
  • 如果要删除一个节点 则要先找删除节点的前一个节点

【代码如下】

    public static Node removeMidNode(Node head) {
//        如果链表长度为空或1则不需要调整直接返回
       if(head==null ||head.next==null){
           return head;
       }
       Node pre=head;
       Node cur=head.next.next;
//       也就是链表长度每增加2 要删除的节点就后移动一个节点。
       while (cur.next != null && cur.next.next != null) {
            pre=pre.next;
            cur = cur.next.next;
       }
        pre.next = pre.next.next;
        return head;
    }

删除链表a/b处的节点

【案列】

  • 1->2->3->4->5,假设a/b的值为r。
  • 如果r等于0,不删除任何节点;
  • 如果r在区间(0,1/5]上,删除节点1;
  • 如果r在区间(1/5,2/5]上,删除节点2;
  • 如果r在区间(2/5,3/5]上,删除节点3;
  • 如果r在区间(3/5,4/5]上,删除节点4;
  • 如果r在区间(4/5,1]上,删除节点5;
  • 如果r大于1,不删除任何节点。

【代码如下】

    public static Node removeByRatio(Node head, int a, int b) {
        if (a < 1 || a > b) {
            return head;
        }
        int n = 0;
        Node cur = head;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        n = (int) Math.ceil(((double) (a * n)) / (double) b);
        if (n == 1) {
            head = head.next;
        }
        if (n > 1) {
            cur = head;
            while (--n != 1) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }

参考资料

如未加特殊说明,转载必须注明出处:印象博客 » 链表算法题练习

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. 测试

    (2019-07-30) 回复