精华内容
下载资源
问答
  • 如何判断链表有环

    千次阅读 2019-03-11 10:26:57
    如何判断单链表是否存在环 ...如何用程序判断出这个链表是有环链表? 不允许修改链表结构。 时间复杂度O(n),空间复杂度O(1)。 方法一、穷举遍历 方法一:首先从头节点开始,依次遍历单链表的每...

    转自:https://blog.csdn.net/u010983881/article/details/78896293

    如何判断单链表是否存在环

    有一个单向链表,链表当中有可能出现“环”,就像题图这样。如何用程序判断出这个链表是有环链表?

    • 不允许修改链表结构。
    • 时间复杂度O(n),空间复杂度O(1)。

    方法一、穷举遍历

    方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的节点,就继续遍历下一个新节点,继续重复刚才的操作。

    例如这样的链表:A->B->C->D->B->C->D, 当遍历到节点D的时候,我们需要比较的是之前的节点A、B、C,不存在相同节点。这时候要遍历的下一个新节点是B,B之前的节点A、B、C、D中恰好也存在B,因此B出现了两次,判断出链表有环。

    假设从链表头节点到入环点的距离是D,链表的环长是S。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)*(D+S)/2 , 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间,空间复杂度可以简单地理解成为O(1)。

    方法二、哈希表缓存

    **首先创建一个以节点ID为键的HashSet集合,用来存储曾经遍历过的节点。然后同样是从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就用新节点和HashSet集合当中存储的节点作比较,如果发现HashSet当中存在相同节点ID,则说明链表有环,如果HashSet当中不存在相同的节点ID,就把这个新节点ID存入HashSet,之后进入下一节点,继续重复刚才的操作。

    这个方法在流程上和方法一类似,本质的区别是使用了HashSet作为额外的缓存。

    假设从链表头节点到入环点的距离是D,链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S,可以简单理解为O(N)。而算法的空间复杂度还是D+S-1,可以简单地理解成O(N)。

    方法三、快慢指针

    首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。

    例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,指针1移动到了节点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指针2移动到了节点B。第三轮循环,指针1移动到了节点D,指针2移动到了节点D,此时两指针指向同一节点,判断出链表有环。

    此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身后再次追上并超过,原因很简单,因为跑道是环形的。

    /**
     * 判断单链表是否存在环
     * @param head
     * @return
     */
    public static <T> boolean isLoopList(ListNode<T> head){
        ListNode<T> slowPointer, fastPointer;
    
        //使用快慢指针,慢指针每次向前一步,快指针每次两步
        slowPointer = fastPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
    
            //两指针相遇则有环
            if(slowPointer == fastPointer){
                return true;
            }
        }
        return false;
    }
     
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    假设从链表头节点到入环点的距离是D,链表的环长是S。那么循环会进行S次(为什么是S次,有心的同学可以自己揣摩下),可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所以空间复杂度是O(1)。

    如何找出有环链表的入环点?

    根据这篇文章:链表中环形的入口,我们来分析一下入环口和我们上面这个快慢指针相遇点的关系。

    当fast若与slow相遇时,slow肯定没有走遍历完链表(不是一整个环,有开头部分,如上图)或者恰好遍历一圈(未做验证,看我的表格例子,在1处相遇)。于是我们从链表头、相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点(慢指针走了n步,第一次相遇在c点,对慢指针来说n=s+p,也就是说如果慢指针从c点再走n步,又会到c点,那么顺时针的CB距离是n-p=s,但是我们不知道s是几,那么当快指针此时在A点一步一步走,当快慢指针相遇时,相遇点恰好是圆环七点B(AB=CB=s))。

    /**
     * 找到有环链表的入口
     * @param head
     * @return
     */
    public static <T> ListNode<T> findEntranceInLoopList(ListNode<T> head){
        ListNode<T> slowPointer, fastPointer;
    
        //使用快慢指针,慢指针每次向前一步,快指针每次两步
        boolean isLoop = false;
        slowPointer = fastPointer = head;
        while(fastPointer != null && fastPointer.next != null){
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
    
            //两指针相遇则有环
            if(slowPointer == fastPointer){
                isLoop = true;
                break;
            }
        }
    
        //一个指针从链表头开始,一个从相遇点开始,每次一步,再次相遇的点即是入口节点
        if(isLoop){
            slowPointer = head;
            while(fastPointer != null && fastPointer.next != null){
                //两指针相遇的点即是入口节点
                if(slowPointer == fastPointer){
                    return slowPointer;
                }
    
                slowPointer = slowPointer.next;
                fastPointer = fastPointer.next;
            }
        }
        return null;
    }
     
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    如何判断两个单链表是否相交,以及相交点

    方法一、直接法

    直接判断第一个链表的每个结点是否在第二个链表中,时间复杂度为O(len1*len2),耗时很大

    方法二、利用计数

    如果两个链表相交,则两个链表就会有共同的结点;而结点地址又是结点唯一标识。因而判断两个链表中是否存在地址一致的节点,就可以知道是否相交了。可以对第一 个链表的节点地址进行hash排序,建立hash表,然后针对第二个链表的每个节点的地址查询hash表,如果它在hash表中出现,则说明两个链表有共 同的结点。这个方法的时间复杂度为:O(max(len1+len2);但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度,增加 了存储空间。

    以链表节点地址为值,遍历第一个链表,使用Hash保存所有节点地址值,结束条件为到最后一个节点(无环)或Hash中该地址值已经存在(有环)。

    再遍历第二个链表,判断节点地址值是否已经存在于上面创建的Hash表中。
    这个方面可以解决题目中的所有情况,时间复杂度为O(m+n),m和n分别是两个链表中节点数量。由于节点地址指针就是一个整型,假设链表都是在堆中动态创建的,可以使用堆的起始地址作为偏移量,以地址减去这个偏移量作为Hash函数

    方法三、利用有环链表思路

    对于两个没有环的链表相交于一节点,则在这个节点之后的所有结点都是两个链表所共有的。如果它们相交,则最后一个结点一定是共有的,则只需要判断最后一个结点是否相同即可。时间复杂度为O(len1+len2)。对于相交的第一个结点,则可求出两个链表的长度,然后用长的减去短的得到一个差值 K,然后让长的链表先遍历K个结点,然后两个链表再开始比较。

    还可以这样:其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个

    参考资料

    展开全文
  • 判断链表是否存在环形链表

    千次阅读 2015-09-25 10:12:36
    如何解决链表中是否存在链表的问题: 设置两个指针p1, p2,每次p1向前走一步,p2向前走两步,直到p2碰到NULL或两个指针相等时结束循环。 如果两个指针相等,则说明该链表存在环。

    如何解决链表中是否存在链表的问题:

    设置两个指针p1, p2,每次p1向前走一步,p2向前走两步,直到p2碰到NULL或两个指针相等时结束循环。

    如果两个指针相等,则说明该链表存在环。

    程序实现:

    //判断链表是否存在环
    bool isLoop(ListNode *head) {
    	ListNode *p1, *p2;
    	p1 = p2 = head->next;
    	if(head == NULL || head->next == NULL) {
    		return false;
    	}
    	do{
    		p1 = p1->next;				//p1走一步 
    		p2 = p2->next->next;		//p2走两步 
    	}while(p2 && p2->next && p1 != p2);
    	if(p1 == p2) {
    		return true;
    	} else {
    		return false;
    	}
    } 

    测试用例:

    int main()
    {
    	int pos, data;
    	ListNode *head, *item, *p, *q;
    	head = create_list();
    	cout << endl;
    	print_list(head);
    	p = head->next;
    	if(p != NULL) {
    		q = p->next;
    	}
    	
    	while(q) {
    		p = p->next;
    		q = q->next;
    	}
    	p->next  = head->next;
    	bool flag = isLoop(head);
    	cout << "list is loop ? " << flag << endl;
    }




    展开全文
  • 判断链表是否为回文链表

    千次阅读 2018-12-02 11:44:54
    2. 解决的方法有两种,一种是将链表进行翻转(这里可以使用递归来解决)然后翻转后的后半部分与链表的前半部分进行比较来进行判断,第二种是将先找到链表的中间位置,这里可以使用快慢指针指针来进行,快指针一次走...

    1. 问题描述:

    给出一个链表,判断该链表是否为回文链表

    2. 解决的方法有两种,一种是将链表进行翻转(这里可以使用递归来解决)然后翻转后的后半部分与链表的前半部分进行比较来进行判断,第二种是将先找到链表的中间位置,这里可以使用快慢指针指针来进行,快指针一次走一步,慢指针一次走两步,那么等到快指针走到末尾的时候那么慢指针的位置是链表的中间位置,在求出中间位置的时候对慢指针指向的元素进行压栈,等到循环结束那么堆栈里面存储的是链表的前半部分的元素,这里需要注意的时候需要在循环中判断链表的节点是奇数还是偶数,假如是奇数那么慢指针应该再走一步,因为判断回文假如是奇数的节点的话中间那个元素是不用进行判断的

    最后进行出栈,将出栈的元素与链表后半部分的元素进行比较发现不同直接返回false,等到循环结束还没有返回说明就是回文链表返回true就可以了

    这里利用到的是栈这个数据结构和栈先进后出的特点,所以很巧妙地解决了比较的问题

    3. 具体的代码如下:

    import java.util.Stack;
    public class Main{
    	private static class ListNode{
    		private ListNode next;
    		int value;
    		public ListNode(int value) {
    			super();
    			this.value = value;
    		}
    	}
    	
    	public static void main(String[] args) {
    		ListNode node = new ListNode(1);
    		node.next = new ListNode(2);
    		node.next.next = new ListNode(3);
    		node.next.next.next = new ListNode(2);
    		node.next.next.next.next = new ListNode(1);
    		node.next.next.next.next.next = new ListNode(5);
    		ListNode p = node;
    		while(p != null){
    			System.out.print(p.value + " ");
    			p = p.next;
    		}
    		System.out.print("\n");
    		boolean res = plalinDromeLinkedList(node);
    		System.out.println(res);
    	}
    
    	private static boolean plalinDromeLinkedList(ListNode node) {
    		//有两种方法可以解决一种是翻转链表进行比较,另外一种是将链表前半部分进行压栈然后进行弹栈与后半部分的节点进行比较
    		//所以要使用到一种数据结构就是栈
    		ListNode slow = node;
    		ListNode fast = node;
    		boolean isOdd = true;
    		Stack<Integer> stack = new Stack<>();
    		while(fast != null && fast.next != null){
    			//快的一次走两步,慢的一次走一步那么最后快的结束了慢的走了一半,此时在走的过程中需要压栈
    			stack.push(slow.value);
    			slow = slow.next;
    			fast = fast.next.next;
    			if(fast == null){
    				isOdd = false;
    			}
    		}
    		//假如是奇数慢指针需要再走一步
    		if(isOdd) slow = slow.next;
    		while(!stack.isEmpty()){
    			//出栈
    			if(stack.pop() != slow.value){
    				return false;
    			}
    			slow = slow.next;
    		}
    		return true;
    	}
    }
    

     

    展开全文
  • 判断链表是否相交

    2014-10-16 17:13:47
    判断两个单链表是否相交,如果相交,给出相交的...二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个
    判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。
    

    比较好的方法有两个:

    一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。

    二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。

    这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。

      我们学一个算法,一定是为了用吧,所谓“学以致用”吗?那么判断两个链表是否相交有什么用呢?这是因为一旦两个链表出现相交的情况,就可能发生这样的情况,程序释放了链表La的所有节点,这样就导致了另外一个与之有相交节点的链表Lb中的节点也释放了,而Lb的使用者,可能并不知道事实的真相,这会带来很大的麻烦。

    1.问题分析

      看看两个链表相交到底是怎么回事吧,有这样的的几个事实:(假设链表中不存在环)

      (1)一旦两个链表相交,那么两个链表中的节点一定有相同地址。

      (2)一旦两个链表相交,那么两个链表从相交节点开始到尾节点一定都是相同的节点。

      分析出来了问题的本质,那么思路也就自然有了。

    2.问题解法

    2.1 哈希解法:

      既然连个链表一旦相交,相交节点一定有相同的内存地址,而不同的节点内存地址一定是不同的,那么不妨利用内存地址建立哈希表,如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是:遍历第一个链表,并利用地址建立哈希表,遍历第二个链表,看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。

      时间复杂度O(length1 + length2)

      空间复杂度O(length1)

      分析:时间复杂度是线性的,可以接受,并且可以顺便找到第一个相交节点,但是却增加了O(length1)的空间复杂度,这显然不能令人满意。

    2.2 问题转化

      如果两个链表中存在相交节点,那么将第二个链表接到第一个链表的后面,然后从第二个链表的表头开始遍历,如果存在环,则遍历过程一定会回到链表二的表头节点。可是这种方法似乎并不能找到第一个相交节点。怎么办呢?怎样才能判断链表中是否存在环,并且找到环的开始节点呢?

      网上看到了这样的一个解法:设置两个指针fast和slow,初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表),这样就可以判断两个链表是否相交了,程序如下:

    bool IsExitsLoop(slist  * head)
    {
      slist 
    * slow  =  head * fast = head;

      while  ( fast  &&  fast -> next ) 
      {
        slow 
    =  slow -> next;
        fast 
    =  fast -> next -> next;
        if  ( slow  ==  fast )
          break ;
      }
      return  ! (fast  ==  NULL  ||  fast -> next  ==  NULL);
    }

    下面看看怎么找环的入口,当fast与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
    2s = s + nr
    s= nr

    设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
    a + x = nr
    a + x = (n – 1)r +r = (n-1)r + L - a
    a = (n-1)r + (L – a – x)

    (L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点(从相遇点向后遍历循环回到入口点的距离),于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇点为环入口点,也即为两个链表的第一个相同节点。程序描述如下:

    复制代码
    slist* FindLoopPort(slist *head)
    {
        slist *slow = head, *fast = head;
        while ( fast && fast->next ) 
        {
             slow = slow->next;
             fast = fast->next->next;
             if ( slow == fast )  break;
        }
        if (fast == NULL || fast->next == NULL)
            return NULL;
        slow = head;
        while (slow != fast)
        {
             slow = slow->next;
             fast = fast->next;
        }
        return slow;
    }
    复制代码

    这种解法似乎是非常犀利,逻辑推理很棒,但是这种解法的时间复杂度是怎么样的呢??slow每次前进一步,fast每次前进两步,这样的话遍历多少步会结束呢???(求人解释)

    2.3 抓住要点

      不妨遍历每个链表保存最后一个节点,看看最后一个节点是否是同一个节点,这种情况时间复杂度是O(length1 + length2)。基本也不需要什么空间,似乎是一个不错的想法哦,那么怎么找到第一个相交节点呢?可以遍历的过程中记录链表的长度L1和L2(假设L1>L2)这是遍历找到第一个链表中的第L1 - L2节点,然后链表一从第L1-L2个节点开始遍历,链表二从第一个节点遍历,每次前进一步,直到找到第一个相同的节点,则可以认为两个链表存在相交节点,并且该点即为第一个相交节点(原来这里写错了,感谢Ider指出这个错误)。这种解法的时间复杂度也是线性的,但是如果两个链表长度相差不多时,时间复杂度还是不错的。

      到这里,我知道的几种典型的解法就说完了。欢迎大神们提供新的思路!!

    3.问题扩展:(思考)

      baidu曾经出过这样的一个笔试题目,归根到底也是找到两个链表是否存在相同的节点,但是数据量很大,即链表长度是上亿的。想想那么应该怎么处理呢?

    问题描述:

    一个比较经典的问题,判断两个链表是否相交,如果相交找出他们的交点。

    image

    思路:

    1、碰到这个问题,第一印象是采用hash来判断,将两个链表的节点进行hash,然后判断出节点,这种想法当然是可以的。

    2、当然采用暴力的方法也是可以的,遍历两个链表,在遍历的过程中进行比较,看节点是否相同。

    3、第三种思路是比较奇特的,在编程之美上看到的。先遍历第一个链表到他的尾部,然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表,判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了:即判断单链表是否有环?

    这样进行转换后就可以从链表头部进行判断了,其实并不用。通过简单的了解我们就很容易知道,如果新链表是有环的,那么原来第二个链表的头部一定在环上。因此我们就可以从第二个链表的头部进行遍历的,从而减少了时间复杂度(减少的时间复杂度是第一个链表的长度)。

    下图是一个简单的演示:

    image

    这种方法可以判断两个链表是否相交,但不太容易找出他们的交点。

    4、仔细研究两个链表,如果他们相交的话,那么他们最后的一个节点一定是相同的,否则是不相交的。因此判断两个链表是否相交就很简单了,分别遍历到两个链表的尾部,然后判断他们是否相同,如果相同,则相交;否则不相交。示意图如下:

    image

    判断出两个链表相交后就是判断他们的交点了。假设第一个链表长度为len1,第二个问len2,然后找出长度较长的,让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值),然后在开始遍历两个链表,判断节点是否相同即可。

    下面给出一个简单的实现:


    typedef struct node_t
    
    {
    
    int data;//data
    
    struct node_t *next; //next
    
    }node;
    
     
    
    node* find_node(node *head1, node *head2)
    
    {
    
    if(NULL == head1 || NULL == head2)
    
    {
    
    return NULL;//如果有为空的链表,肯定是不相交的
    
    }
    
    node *p1, *p2;
    
    p1 = head1;
    
    p2 = head2;
    
    int len1 = 0;
    
    int len2 =0;
    
    int diff = 0;
    
    while(NULL != p1->next)
    
    {
    
    p1 = p1->next;
    
    len1++;
    
    }
    
    while(NULL != p2->next)
    
    {
    
    p2 = p2->next;
    
    len2++;
    
    }
    
    if(p1 != p2) //如果最后一个节点不相同,返回NULL
    
    {
    
    return NULL;
    
    }
    
    diff = abs(len1 - len2);
    
    if(len1 > len2)
    
    {
    
    p1 = head1;
    
    p2 = head2;
    
    }
    
    else
    
    {
    
    p1 = head2;
    
    p2 = head1;
    
    }
    
    for(int i=0; i<diff; i++)
    
    {
    
    p1 = p1->next;
    
    }
    
    while(p1 != p2)
    
    {
    
    p1 = p1->next;
    
    p2 = p2->next;
    
    }
    
    return p1;
    
    }

    通过上面的操作就可以找到两个链表的交点了。

    5、总结

    上面的几种方法中最后一种是比较不错的,当然hash也是可以的。

    问题的延伸:

    如果原来的两个链表中有环怎么处理?



    展开全文
  • 判断链表是否带环

    2013-12-19 20:47:26
    判断链表是否带环 2009-08-28 16:18 有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。 问题: 1、如何判断一个链表是不是这类链表? 2、如果链表...
  • 判断链表是否有环

    2016-07-27 21:14:41
    有一个链表,我们需要判断链表中是否存在环。有环则输出true,否则输出false。 输入有多行,每行为由空格分隔的两个整数m和n,m是当前结点的数据,n代表当前结点的指针域指向第n个结点。 n存在四种情形: ①为-1...
  • 有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表...一、判断链表是否存在环,办法为: 设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则f
  • 判断链表是否有环,判断环的入口

    千次阅读 2018-09-13 16:59:44
    问题1:判断链表是否有环 问题分析 首先考虑环出现之后链表的特征,从头开始的链表遍历无法结束,也就是不存在尾节点 这时候第一个想法,一遍遍历链表,直至出现null 或者下一个元素是之前出现过的元素,那么...
  • 设计算法判断链表是否中心对称

    千次阅读 2020-03-20 11:36:13
    算法思想:使用栈来判断链表中的数据是否中心对称。让链表的前一半元素依次进栈,在处理链表的后一半元素的时,当访问到链表的一个元素时,就从栈中弹出一个元素,两个元素比较,若相同,则将链表的下一个元素与栈中...
  • 给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 示例 1: 输入:head = [3,2,0,-4], pos ...
  • 判断链表中环的存在

    2012-10-25 08:57:02
    一、判断链表是否存在环,办法为: 设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行...
  • 【算法】如何判断链表有环

    万次阅读 多人点赞 2017-12-25 20:05:59
    如何用程序判断出这个链表是有环链表? 不允许修改链表结构。 时间复杂度O(n),空间复杂度O(1)。 方法一、穷举遍历方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点...
  • 今天看到这么一道面试题,问如何判断一个链表是否
  • 今天做到leetcode 141: Linked List Cycle,判断链表是否存在环,因为看到题目中的val都是整数,所以我是将每个node用1.1作为值去mark了,如果head.next的val是1.1,就说明我指向的下个结点已经走过了,这就是一个环...
  • 最近在看程序员面试金典,在链表部分看到有一题问如何判断链表是否是回文串,然后想到白书中也有对最长回文子串的讨论,故想做一点总结。 一、判断链表是否为回文串 链表的数据结构是这样子滴: ...
  • 如何判断链表有环(三种方法)

    千次阅读 2019-06-02 09:16:15
    方法一、穷举遍历 ...点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的 节点,就继续遍历下一个新节点,继续重复刚才的操作。 例如这样的链表:A->B->...
  • 如何判断链表中有环

    2017-01-03 11:45:17
    一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接,链表最基本的结构是在每个节点保存数据和到下一个节点的地址,在最后一个节点保存一个特殊的结束标记,另外在一个固定的位置保存指向第一个节点的...
  • 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。 什么是回文:正读,反读都一样的句子,字符串,...
  • 判断两个链表是否相交  2012-01-09 10:37:03| 分类: 默认分类|字号 订阅 给出两个单向链表的头指针,判断这两个链表是否相交,如果相交给出相交的第一个结点 一、两个链表均不含有环 ...
  • 判断链表有没有环

    2013-12-10 20:02:31
    二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。 这时我们记下两个链表length...
  • 【问题描述】学习链表,销毁链表总感觉没有成功,请问怎么确定链表确实被销毁了?为什么其余节点的内容没有变化? 【代码】 ``` #include #include #include struct link_list { int num; char name[20...
  • leetcode解题之141# Linked List Cycle Java版 (判断链表是否有环)
  • 有一个链表,我们需要判断链表中是否存在环。有环则输出true,否则输出false。 输入有多行,每行为由空格分隔的两个整数m和n,m是当前结点的数据,n代表当前结点的指针域指向第n个结点。 n存在四种情形: ①为-1...
  • 判断给定的链表是否存在环;

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 106,169
精华内容 42,467
关键字:

如何判断链表结束