LeetCode-61

题目

61. 旋转链表

结果

代码

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 特殊情况
        if (head == null) {
            return null;
        }
        if (k == 0) {
            return head;
        }

        // 求出链表长度
        int len = listLength(head);

        // 将链表的首尾相接，形成循环链表
        tailToHead(head);

        // 链表右移，指针应左移，所以取 “补码”
        k = len - k % len;
        for (int i = 0; i < k; i++) {
            head = head.next;
        }

        ListNode ans = new ListNode(0);
        ListNode p = ans;
        for (int i = 0; i < len; i++, head = head.next, p = p.next) {
            p.next = new ListNode(head.val);
        }
        return ans.next;
    }

    private int listLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    private void tailToHead(ListNode head) {
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = head;
    }
}

• Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
	n := length(head)
    if n == 0 {
		return head
	}
	k = k % n
	if k == 0 || k == n {
		return head
	}

	tail := kthNode(head, n-1)
	kth := kthNode(head, n-k-1)

	trueHead := kth.Next
	kth.Next = nil
	tail.Next = head
	return trueHead
}

func length(head *ListNode) (length int) {
	for p := head; p != nil; p = p.Next {
		length++
	}
	return
}

// return the kth node of the linked list
func kthNode(head *ListNode, k int) (n *ListNode) {
	n = head
	for i := 0; i < k; i++ {
		n = n.Next
	}
	return
}

复杂度

时间复杂度：O（n），只有遍历链表的操作

空间复杂度：O（n）