首页 > 试题广场 >

转动链表

[编程题]转动链表
  • 热度指数：20266 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
将给定的链表向右转动k个位置，k是非负数。
例如：
给定1->2->3->4->5->null ， k=2，
返回4->5->1->2->3->null。
示例1

输入

{1,2},1

输出

{2,1}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
wanbf头像 wanbf 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode rotateRight (ListNode head, int k) {
        // write code here
        if(head==null || k==0) return head;
        //双指针
        ListNode slow = head;
        ListNode fast = head;
        while(k>0){
            if(fast == null) fast=head;
            fast =fast.next;
            k--;
        }
        if(fast == null) return head;
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        ListNode temp =slow.next;
        slow.next=null;
        fast.next=head;
        return temp;
    }
}

发表于 2022-01-14 01:00:03 回复(0)
Java
悟空2017头像 悟空2017
ListNode tail = new ListNode(-1);
    ListNode newHead = new ListNode(-1);
    public ListNode rotateRight (ListNode head, int k) {
        // write code here
        if (head == null || k==0){
            return head;
        }
        newHead.next = head;
        rotateRightHelper(head,k);
        tail.next.next = head;
        return newHead.next;
    }
    
    public void rotateRightHelper (ListNode head, int k) {
        if(head.next == null){
            tail.next = head;
            return;
        }
        rotateRight(head.next,k-1);
        if(k == 0){
            newHead.next = head.next;
            head.next = null;
        }
    }
发表于 2021-01-14 12:40:22 回复(1)
Java
日常不想上班的码农头像 日常不想上班的码农 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
   /**
	 * 思路：将一个链表从待旋转节点分开，如 1 -> 2 -> 3 -> 4 ->5 旋转2次的结果 4 ->5 -> 1 -> 2 -> 3
	 * 可以看做 4->5 + 1 -> 2 -> 3,即从3的位置分开
	 * @param head
	 * @param k
	 * @return
	 */
	public ListNode rotateRight(ListNode head, int k) {
		// 不旋转
		if (head == null || k == 0) {
			return head;
		}
		// 获取链表长度
		ListNode cur = head;
		int len = 0;
		while (cur != null) {
			cur = cur.next;
			len++;
		}
		k = k % len;
		// 不旋转
		if (k == 0) {
			return head;
		}
		// pre为待旋转节点的前一个节点
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		ListNode pre = dummy;
		int now = 0;
		while (pre != null) {
			pre = pre.next;
			now++;
			if (now == len - k) {
				break;
			}
		}
		ListNode tempNode = pre.next;
		pre.next = null;

		// 开始旋转
		ListNode secondDummy = new ListNode(0);
		secondDummy.next = tempNode;

		while (tempNode.next != null) {
			tempNode = tempNode.next;
		}
		tempNode.next = dummy.next;
		return secondDummy.next;
	}

}

编辑于 2020-08-02 12:22:57 回复(0)
Java
HW柯可头像 HW柯可 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head == null || head.next == null || n == 0)
            return head;
        int len = 0;
        ListNode temp = head;
        //遍历到链表尾部，得到链表长度
        while(temp != null){
            temp = temp.next;
            len ++;
        }
        if(n == len)
            return head;
        if(n > len){
            n = n % len;
        }
        int index = len - n;
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null && index > 0){
            pre = cur;
            cur = cur.next;
            index --;
        }
        pre.next = null;  //中间断链
        ListNode newhead = cur;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = head;   //原链表尾部指向原链表头部
        return newhead;
    }
}

发表于 2020-06-20 18:05:34 回复(0)
Java
装糊涂是极难的艺术#头像 装糊涂是极难的艺术# 
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head == null || head.next == null || n <= 0){
            return head;
        }
        ListNode start = head, end = head;
        for(int i = 0; i< n; i++){
            end = end.next;
            if(end == null){
                end = head;
            }
        }
        if(end == head){
            return head;
        }
        while(end.next != null){
            start = start.next;
            end = end.next;
        }
        ListNode tmp = start.next;
        start.next = null;
        end.next = head;
        return tmp;
    }
}

发表于 2018-05-10 17:22:45 回复(0)
Java
七仔0312头像 七仔0312 
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if (head == null)
            return head;
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
            if (fast == null)
                fast = head;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        fast.next = head;
        ListNode newH = slow.next;
        slow.next = null;
        return newH;
    }
}
发表于 2018-03-17 21:35:12 回复(0)
Java
AMMOK头像 AMMOK 
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head==null||head.next==null)return head;
       for(int i =1;i<=n;i++){
           ListNode p = head;
           ListNode p1=head;
           ListNode p2 = null;
        while(p1.next!=null){
            if(p1.next.next==null){
                p2 =p1;
            }
            p1=p1.next;
        }
        p2.next=null;
        p1.next=p;
        head=p1;
        
       }
       return head;
    }
}

发表于 2017-12-09 20:28:49 回复(0)
Java
无名huster头像 无名huster 
//首先要看k的值是否大于链表长度，如果大于链表长度，则取余确定右边第几个节点为head
//将最后一个节点的next指向原来的head，这样成为了一个环，
//之后遍历到新head的前一个节点将前一个节点的next赋值为null，最后返回新head
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head == null || n < 0){
            return head;
        }
        int length = 1;
        ListNode node = head;
        //获得链表长度
        while(node.next!=null){
            ++length;
            node = node.next;
        }
        //获得右边第i个下标
        int k = n % length;
        //将最后一个节点指向head，形成一个环
        node.next = head;
        //接下来的遍历节点数
        int num = length - k;
        for(int i=0;i<num;i++){
            node = node.next;
        }
        //得到新节点
        head = node.next;
        node.next = null;
       return head;
    }
}

发表于 2017-09-05 16:43:58 回复(1)
Java
萨仁朝格图（大家去脉脉沟通）头像 萨仁朝格图（大家去脉脉沟通） 
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        ListNode p = head,end = null; int num = 0;
        if(p==null)return p;
        while(p!=null){
            num++;
            end = p;
            p = p.next;            
        }
        if(n%num == 0)return head;
        int i = 1; p = head;
        while(i < num-n%num){
            p = p.next;
            i++;
        }
        ListNode q = p.next;
        end.next = head;
        p.next = null;
        return q;
    }
}

发表于 2017-08-14 20:49:12 回复(1)
Java
Holiday_12138头像 Holiday_12138 
public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head == null || n == 0)
            return head;
        int num = 1;
        ListNode cur = head;
        while(cur.next != null) {
            num++;
            cur = cur.next;
        }
        n %= num;
        if(n == 0)
            return head;
        cur.next = head;
        for(int i=0; i<num-n; i++) {
            cur = cur.next;
        }
        head = cur.next;
        cur.next = null;
        return head;
    }
}

发表于 2017-06-20 16:02:28 回复(0)
Java
吉吉国王头像 吉吉国王
使用快慢指针，先找到倒数第n个节点，然后改变指针 

public static ListNode rotateRight(ListNode head, int n) {
        if (head == null)   //空
            return null;
        ListNode fast, slow;    //快慢指针
        fast = slow = head;
        int lenOfList = getLen(head);   //获取链表长度
        int k = n % lenOfList;  //取余
        if (k == 0) //不变
            return head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        //slow指向前半段的最后一个,fast指向后半段最后一个
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;   //变成最后一个
        fast.next = head;   //连上head
        return newHead;
    }
    //获取链表长度
    private static int getLen(ListNode head) {
        ListNode p = head;
        int len = 0;
        while (p != null){
            len++;
            p = p.next;
        }
        return len;
    }

发表于 2017-04-11 23:02:28 回复(0)
Java
城市里的养猫者头像 城市里的养猫者

Since n may be a large number compared to the length of list. So we need to know the length of linked list.After that, move the list after the (l-n%l )th node to the front to finish the rotation.

Ex: {1,2,3} k=2 Move the list after the 1st node to the front

Ex: {1,2,3} k=5, In this case Move the list after (3-5%3=1)st node to the front.

So the code has three parts.

  1. Get the length

  2. Move to the (l-n%l)th node

3)Do the rotation 

public ListNode rotateRight(ListNode head, int n) { if (head==null||head.next==null) return head;
    ListNode dummy=new ListNode(0);
    dummy.next=head;
    ListNode fast=dummy,slow=dummy; int i; for (i=0;fast.next!=null;i++)//Get the total length  fast=fast.next; for (int j=i-n%i;j>0;j--) //Get the i-n%i th node slow=slow.next;
    
    fast.next=dummy.next; //Do the rotation dummy.next=slow.next;
    slow.next=null; return dummy.next;
}
发表于 2017-03-12 12:25:42 回复(0)
提交观点

问题信息

链表
难度：
14条回答 16371浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号