欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 61. Rotate List

程序员文章站 2022-04-06 15:33:48
...

Rotate List算法思路:
首先,给链表加上一个虚拟头结点,利用双索引找到倒数第k+1个结点q和最后一个结点p,则q是转化后最后一个结点,q.next是转化后的第一个节点。利用穿针引线法将其重新连接成一个链表。最终返回的是q.next结点。考虑特殊情况,可以更好地优化算法,如果取余后k值为0或空链表,可直接返回head。
该算法时间复杂度O(n),空间复杂度O(1).。参考代码如下:

	//leetcode   61. Rotate List
    public static ListNode rotateRight(ListNode head, int k) {    
        ListNode vmNode = new ListNode(0);
        vmNode.next = head;
        ListNode p = head,q = vmNode,pre=vmNode;
        int n=0;
        while(p!=null){
        	++n;
        	p = p.next;
        }
        if(n!=0)
        k = k%n;
        if(k==0)
        	return head;
        p = vmNode;
        while((k+1)!=0&&p!=null){
        	pre = p;
        	p = p.next;
        	--k;
        }
        while(p!=null&&q!=null){
        	q = q.next;
        	pre = p;
        	p = p.next;
        }
        ListNode head_q = q.next;
        q.next = null;
        pre.next=head;
    	return head_q;
    }

找到倒数第k个结点并删除该结点的算法:


	//leetcode   19. Remove Nth Node From End of List
    public ListNode removeNthFromEnd(ListNode head, int n) {
    	ListNode vmNode = new ListNode(0);
    	vmNode.next = head;
    	ListNode p = vmNode,q=vmNode;
    	while((n+1) !=0&&p!=null){
    		p = p.next;
    		n--;
    	}
    	while(p!=null){
    		q = q.next;
    		p = p.next;
    	}
    	q.next = q.next.next;
    	return vmNode.next;
    }
相关标签: List