多线程 leetcodeLCP SQLMAP firebase audio types 逻辑端口 vue实例 idea导入多个项目 pythonapi java正则 java实例 java实战 java编译环境 java学习基础 摩斯电码翻译器 彻底删除mysql 迅雷免费会员号共享 图片生成网址 qq免安装版 手机模拟器下载 php购物车 脚本 网络适配器下载 3d软件下载 html5下载 无限视距 猫眼电影票 工程html加密 windowsjs延时函数 一键换肤大师 vue定时器 js动态添加元素 cdlinux教程 淘宝抽奖活动 商标查询软件 su模型交错 mysql定时备份 studio3t 1000kbps
当前位置: 首页 > 学习教程  > 编程语言

数据结构和算法——链表

2020/8/11 21:01:51 文章标签:

本文介绍常见的链表的编程题

删除链表中重复元素(排序链表)

思路:有序链表,遍历当前节点和下一个节点相等,删除即可

public ListNode deleteDuplicates(ListNode head) {
       ListNode list = head;
       while(list!=null){
         if(list.next==null){
         	break;
         }
         if(list.val == list.next.val){
         	list.next = list.next.next;
         }else{
         	list = list.next;
         }
       }
       return head;
    }

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

public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        slow.next=head;
        fast.next=head;
        //fast指针每次多走一步,n+1次多走n+1步
        for (int i = 1; i <= n + 1; i++) {
            fast = fast.next;
        }
        //找到第n+1个节点
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //删除节点
        slow.next = slow.next.next;
        return start.next;
      }
    }

环形链表(给定一个链表,判断链表中是否有环)

思路:快慢指针,一定会相遇

public static boolean hasCycle(ListNode head) {
       if(head==null){
       		return false;
       }
       ListNode fast=head;
       ListNode slow=head;
       while(fast!=null && fast.next!=null){
       		fast=fast.next.next;
       		slow=slow.next;
       		if(slow==fast){
       			return true;
       		}
       }
    	return false;
    }

相交链表:找到两个单链表相交的起始节点

思路:1.消除长度,2.找相同节点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       int lenA = length(headA), lenB = length(headB);
       while(lenA > lenB){
           headA=headA.next;
           lenA--;
       }
        while(lenA < lenB){
           headB=headB.next;
           lenB--;
       }	
       while(headA!=headB){
           headA=headA.next;
           headB=headB.next;
       }
    	return headA;
    }

 private int length(ListNode node) {
        int length = 0;
        while (node != null) {
            node = node.next;
            length++;
        }
        return length;
    }

反转链表

思路:前置节点为NULL,遍历原链表,当前节点的next指向pre,重置pre节点和curr节点

 public ListNode reverseList(ListNode head) {
       ListNode curr = head,pre=null;
       while(curr!=null){
           ListNode next=curr.next;
           curr.next=pre;
           pre=curr;
           curr=next;
       }
     	return pre;
    }

回文链表

思路:使用快速和慢速指针查找列表的中间位置。这意味着当快速指针到达最后一个末尾时,慢速指针将到达中间,然后反转最后一半,并将列表前半部分中的每个元素与后半部分中的元素进行比较。

public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) {
            slow = slow.next;
        }
        //后半部分
        slow = reverse(slow);
        while (slow != null && head.val == slow.val) {
            head = head.next;
            slow = slow.next;
        }
        return slow == null;
    }

链表的中间节点

思路:双指针

public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
    		return slow;
    }

本文链接: http://www.dtmao.cc/news_show_100459.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?