精华内容
下载资源
问答
  • 算法总结之 删除链表的中间节点和a/b处的节点(链表中间节点的重要思想) 给定链表的表头节点head,实现删除链表的中间节点的函数 推展: 给定链表的头节点,整数a 和 整数 b,实现删除a/b处节点的...

    算法总结之 删除链表的中间节点和a/b处的节点(链表中间节点的重要思想)

    给定链表的表头节点head,实现删除链表的中间节点的函数

     

    推展: 给定链表的头节点,整数a 和 整数 b,实现删除a/b处节点的函数

     

    先来分析原问题,

     长度1  直接返回

     长度2 将头节点删除

     长度3 删除第二个  长度4 删除第二个  长度5 删除第三个。。。。。。长度每增加2 删除的节点就向后移动一个节点

    如果要删除一个节点,则需要找到待删除节点的前一个节点

    package TT;
    
    
    public class Test87 {
    
    	public class Node{
    		public int value;
    		public Node next;
    		
    		public Node(int data){
    			this.value = data;
    		}		
    	}
    	
    	public static Node removeMidNode(Node head){
    		if(head==null || head.next == null){
    			return head;
    		}
    		if(head.next.next == null){
    			 return head.next;
    		}
    		Node pre = head;
    		Node cur = head.next.next;
    		while(cur.next !=null & cur.next.next != null){
    			pre=pre.next;
    			cur=cur.next.next;
    		}
    		pre.next = pre.next.next;
    		return head;
    		
    	}
    	
    }
    

      

     公式的套用计算 double r = ((double)(a*n))/((double)b)    n代表链表长度   向上取整就ok   然后计算删除第几个节点 找到需要删除节点的前一个节点即可

    package TT;
    
    import TT.Test85.Node;
    
    
    public class Test87 {
    
        public 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;
        }
        
        
    }

     

    posted @ 2017-09-09 19:24 toov5 阅读( ...) 评论( ...) 编辑 收藏
    展开全文
  • 快慢指针法 快慢指针法在寻找链表中间节点这道题上的的思路是这样:通过两个指针遍历链表,快指针每次走2步,慢指针每次走1步,那么当快指针走到链表尾部的时候,慢指针恰好走到链表的中间节点,然后遍历结束,返回...

    1. 碎碎念

    遥想后端君当年,曾经也是学校ACM队的一员,但参加过级别最高的比赛,同时也是ACM方面获得的最大成就,不过是天梯赛三等奖(当时天梯赛在浙江还只是省B级别的,现在已经算国赛了),犹记得当时的分数是120多分,满分是200还是160来着我忘记了,反正成绩比平均分高了大概20分。

    现在回想起来,总体还是感觉自己是个打酱油的,普通的算法题做做还行,难的比如动态规划、贪心、搜索、图论啥的,就不太会了。

    2fc575f332062059d2541e701d9be069.png

    而如今的大厂面试,几乎都会有笔试轮,让现场手写算法题,要是笔试都没过,那与面试官手撕HashMap、JVM、各种框架原理都没有机会上演。由此可见算法的重要性,所以后端君决定开始重学数据结构与算法,每天都会抽出一个小时时间来练习。

    a5a2f434ed7232972396fdef47cb8312.png

    2. 题目

    今天练习的主题是快慢指针法,对应LeetCode上的题目是第876题——链表的中间结点。

    题目的要求是给定一个链表的头结点head,返回这个链表的中间节点。

    给定的链表数据结构为

    例如,当链表为[1,2,3,4,5]时,返回的是值为3的节点;当链表为[1,2,3,4,5,6]时,返回的是值为4的节点。

    当然我们可以先遍历一遍链表,得到链表的长度,然后计算出中间节点的索引值,最终通过迭代去获得中间节点。

    这样虽然最终也能得到结果,但怎么说呢,不优雅。

    334c4425f00dfefb471dd0974e9fc72f.png

    而下面要讲的快慢指针法,只需要通过一次遍历就能够得到答案,相对来说就比较优雅且高效。

    3. 快慢指针法

    快慢指针法在寻找链表中间节点这道题上的的思路是这样:通过两个指针遍历链表,快指针每次走2步,慢指针每次走1步,那么当快指针走到链表尾部的时候,慢指针恰好走到链表的中间节点,然后遍历结束,返回慢指针即为链表中间节点。

    先来看第一个示例,当链表为[1,2,3,4,5]时,灵魂画手上线,这时链表是这样子的(我们用白色的箭头来表示慢指针,黑色的箭头来表示快指针):

    ccf135c24612a7e96e905bc186d82213.png 链表初始状态

    当两个指针经过第1次移动后,快指针走到3的位置,慢指针走到2的位置,这时链表是这样子的:

    405532b8eee0e3c2ea873baa1748299f.png 第1次移动后的链表

    当两个指针经过第2次移动后,快指针走到5的位置,慢指针走到3的位置,这时链表是这样子的:

    873c9f144344eca7e41a60158c16634c.png 第2次移动后的链表

    当要进行第3次移动到,发现快指针已经走到了链表尾部节点,即fast.next == null,于是退出遍历,直接返回慢指针,也就是值为3的节点。

    这时当链表节点数为奇数的时候的题解步骤,若节点数为偶数,就有一些不同的,比如链表为[1,2,3,4,5,6]时,在第3次移动后快指针走到了NULL指针的位置,慢指针走到了4的位置,如下图所示:

    08283a93edf0d63f0feb18d533127a37.png 第3次移动后的链表

    这时候的判断就不是快指针走到链表尾部节点了,而是快指针本身就是一个空节点。

    所以综合链表长度为奇数和偶数的两种情况,遍历链表结束的条件应该是:快指针为空或快指针走到链表尾部节点(即快指针的下一个阶段为空)。

    所以,这道题的快慢指针解法应该是下面这样子。

    4. 拓展

    寻找链表中间节点只是快慢指针法的一种应用,快慢指针法还能够用在很多算法题中,比如寻找链表中倒数第k个节点、判断一个链表是不是环形链表等等。

    这两题的分别是剑指Offer第22题和Leetcode第141题,有兴趣的同学可以去做做。

    5. 小结

    本文通过LeetCode上的一道寻找链表中间节点的题目来描述了一下快慢指针法,这是一个普通却又并不简单的算法。后端君认为,在应用快慢指针法时,我们需要注意的是遍历结束条件以及快慢指针分别如何移动,在确定了这两个步骤之后才能够真正运用这个算法来解决问题。

    今天的快慢指针法,你学会了吗?

    版权声明:本文为Planeswalker23所创,转载请带上原文链接,感谢。

    本文使用 mdnice 排版

    展开全文
  • 找到链表中间节点

    2018-10-22 21:47:00
    问题和删除倒数第k个节点...当p或者p的下一个节点为空时,q指向链表中间节点 代码: int midList(Node * head) {//快慢指针 Node * fast = head; Node * slow = head; while (fast&amp;&amp;fast...

    问题和删除倒数第k个节点类似,如果两次遍历很容易得到结果

    这里可以使用快慢指针的方法

    p每次遍历两个节点,q每次遍历一个节点

    当p或者p的下一个节点为空时,q指向链表的中间节点

    代码:

    int midList(Node * head) {//快慢指针
    	Node * fast = head;
    	Node * slow = head;
    	while (fast&&fast->next) {
    		fast = fast->next->next;
    		slow = slow->next;
    	}
    	return slow->data;
    }

    运行结果

    展开全文
  • 查找链表中间节点

    查找链表中间节点

    微笑一.问题描述

            给点一个链表,返回该链表的中间节点。

    疑问二.问题分析

            假定一个链表中节点数据依次为(单数):1->2->3->4->5->(NULL),基于这个问题,首先我们会想到一种比较low的解决办法:遍历整个链表,得到链表总个数,取链表中值,再遍历一遍链表,找出链表中间节点(节点3)。当你写出这种代码的时候,面试官肯定会让你将其优化,代码执行效率较低。换种角度思考这个问题:假设分别定义一个快指针(走两步)和慢指针(走一步),当快指针遍历完整个链表时,慢指针刚好指向链表中间节点,这样我们通过只遍历一遍链表的方式得到链表中间节点。

    大笑三.问题解决

    1.代码实现

    typedef int DataType;
    //定义结构体
    typedef struct LinkNode
    {
    	DataType data;  //data存放指针数据
    	struct LinkNode *next;   //next为指向链表下一个节点指针域
    }*pLinkNode,*pLinkList;
    
    //查找链表中间节点
    pLinkNode FindMidNode(pLinkList *pHead)
    {
    	assert(*pHead);
    	pLinkNode slow=*pHead;  //慢指针
    	pLinkNode fast=*pHead;  //块指针
    	while(fast && fast->next)    //循环条件缺一不可(缺少程序会崩溃),链表节点个数可能为为奇数或偶数
    	{
    		slow=slow->next;   //慢指针走一步
    		fast=fast->next->next;  //快指针走两步
    	}
    	return slow;  //返回中间节点
    }
    
    2.代码测试

    (1)链表个数为奇数


    (2)链表个数为偶数


    展开全文
  • 2-3删除链表中间节点

    2020-02-29 15:28:08
    删除链表中间节点 解题方法1 如果链表长度为n,令k = n/2向上取整。那么要删除的节点就是第k个节点。 只需要先计算链表长度求k值,然后找到第k-1个节点,然后删除第k个节点。 public class Test { public ...
  • 第一题:找到单链表的中间节点(且时间复杂度为O(1))快慢指针的方法:两个指针同时从头结点出发,快指针一次走2步,慢指针一次走1步,当快指针走完所有节点时,慢指针就恰好是该单链表的中间节点。(要注意单链表...
  • 找到链表中间节点(Java)

    千次阅读 2019-03-14 15:00:19
    给定一个非空的单链表和头节点头,返回链表中间节点。 如果有两个中间节点,返回第二个中间节点。 解决 设置两个指针,一个快指针,每次走两步,一个慢指针,每次走一步,当快指针为空(偶数个节点)或者快指针的...
  • 当快指针走到底的时候,满指针指向的就是链表中间节点。需要注意的是,当链表长度为偶数位的时候,则慢指针指向的是中间偏右的节点,奇数的时候,指向的是中间节点。 if(head == null || head.next == null) ...
  •  给定链表的头节点 head ,实现删除链表中间节点的函数。 例如:  不删除任何节点;  1 -&gt; 2,删除节点1;  1 -&gt; 2 -&gt;3, 删除节点2;  1 -&gt; 2 -&gt;3 -&gt; 4, ...
  • 链表查找中间节点Hello everyone! Today we have great chance to dive more into linked list and its functionality. I hope you already know basics about linked list and methods that it has. Today, we are ...
  • 寻找链表中间节点-一种高效的算法

    千次阅读 2010-07-14 14:35:00
    链表(特别是单链表)的定位是链表这种... <br /> 前一段时间,在看链表的归并排序的时候,就不得不面临着寻找链表中间节点的问题。这里给出一种实现,很可能是大家想不到的:): <br />1) 使用两
  • Given a singly linked list, determine if it is a palindrome. ...找到链表中点,拆分后,逆转后半个链表,然后两个链表同时顺序遍历一次。 不过唯一需要注意的是,当链表长度为奇数,我们需要先将链表中点
  • int IndexForVal(ListNode * pHead, int val) { int index = 1; ListNode *CurrentNode = pHead; while (CurrentNode) ... //找到位置返回 } CurrentNode = CurrentNode->m_pNext; index++; } }
  • 一次遍历单向链表找到中间节点

    千次阅读 2012-11-03 20:19:30
    一次遍历单向链表找到中间节点 具体方法和思想: 1)设置2个指针,一个走2步时,另一个走1步; 2)那么一个走到头时,另一个走到中间。 iNode * GetMiddleNode ( iNode *head ) { iNode *p1 = head; iNode ...
  • 给定链表的头节点head,实现删除链表中间节点的函数。 不删除任何节点 1—>2, 删除节点1 1—>2—>3,删除节点2 1—>2—>3—>4,删除节点2 1—>2—>3—>4—>5,删除节点3 ...
  • LEETCODE很多链表的题目都涉及链表中间节点的查询问题。双指针法是解决这类问题的快速算法。然而双指针法很容易出现越界和其他特殊情况的细节BUG。在此我针对一些典型节点,整理一些算法。仅供参考。
  • 查找链表中间节点、找出有环链表的环开始节点
  • 找到链表中间节点,可以定义两个指针,一个是慢指针slow,另一个是快指针fast。初始,慢指针slow和快指针fast都指向链表的头节点。然后,快指针fast每次向前移动两步,慢指针slow每次向前移动一步,当快指针fast...
  • 返回链表中间结点输入一个链表,输出该链表中倒数第k个结点将两个有序链表合并为一个新的有序链表并返回。以给定值x为基准将链表分割成两部分在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点 反转...
  • 首先要确定链表中有多少个对象,确定之后,找到中间位置的对象,返回指向它的节点。 代码: class Node{ int val; Node next; public Node(int val, Node next){ this.val = val; thi...
  • 2020-11-03:手写代码:链表如何快速找到中间节点?.pdf
  • 1、奇数链表中间节点很好找,直接用双指针即可(fast->next !=NULL,因为快指针一定会跑到倒数第一个节点) 2、偶数连表一般找中间节点会把后边的节点作为中间节点,此时fast必须跑到倒数第一 找中间节点 while...
  • 删除链表中间节点

    2017-05-17 07:37:37
    //删除中间节点就是要找到中间结点的前一个节点 if (head== null ){ return head; } if (head.next== null ){ return head; } Node<T> cur1=head; Node<T> cur2=cur1.next; while (cur2.next!= ...
  • 查找单向链表中间节点

    千次阅读 2019-03-03 23:25:44
    要求时间复杂度O(n),且单向链表的长度未知。 思路: 快慢指针,快指针一次两步,慢指针一步,当快指针到达链表结尾时,慢指针指向的结点即为中间节点 ...
  • 【题目】 1、删除链表中间节点 给定链表的头结点head,实现删除链表中间节点的函数: 例如: 不删除任何节点; 1-->2,删除节点1; 1-->2-->3,删除节点2 1-->... // 找到中间节点 if
  • 【题目】 给定链表的头节点head,实现删除链表中间节点的函数。  例如:  1,不删除任何节点  1 -> 2,删除节点1  1 -> 2 -> 3,删除节点2  1 -> 2 -> 3 -> 4,删除节点2  1 -> 2 -> 3 -> 4 -> 5,...
  • Java实现寻找链表中间节点

    千次阅读 2017-05-23 16:25:50
    利用快慢指针: 设置两个指针slow和fast,两个指针同时向前走,fast指针每次走两步,slow指针每次走...public class l链表中间节点 { public static void main(String[] args){ int[] array = {1,2,3,4,5,6,7,8,9,10
  • 给定一个带有头结点 head 的非空单链表,返回链表中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评...
  • //找链表中间节点 Node *MidNode(PLinkList plist) { PLinkList p1,p2; //若链表为空,直接返回 if(plist ==NULL) { printf( "NULL\n"); return

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,229
精华内容 17,291
关键字:

找到链表的中间节点