FilesExpand file tree

 master

/

RotateList61.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

100 lines (75 loc) · 2.18 KB

 master

/

RotateList61.java

Copy path

Top

File metadata and controls

• Code
• Blame

100 lines (75 loc) · 2.18 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

/**

* Given a list, rotate the list to the right by k places, where k is non-negative.

*

* For example:

* Given 1->2->3->4->5->NULL and k = 2,

* return 4->5->1->2->3->NULL.

*/

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

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

* }

*/

public class RotateList61 {

public ListNode rotateRight(ListNode head, int k) {

if (head == null || k == 0) return head;

ListNode first = head;

ListNode second = head;

int i = 0;

while (i < k && first.next != null) {

first = first.next;

i++;

}

if (first.next == null && i < k) {

return rotateRight(head, k%(i+1));

}

while (first.next != null) {

first = first.next;

second = second.next;

}

ListNode returned = second.next;

first.next = head;

second.next = null;

return returned;

}

/**

* https://discuss.leetcode.com/topic/2861/share-my-java-solution-with-explanation

*/

public ListNode rotateRight2(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;

}

/**

* https://discuss.leetcode.com/topic/26364/clean-java-solution-with-brief-explanation

*/

public ListNode rotateRight3(ListNode head, int k) {

if (head == null)

return head;

ListNode copyHead = head;

int len = 1;

while (copyHead.next != null) {

copyHead = copyHead.next;

len++;

}

copyHead.next = head;

for (int i = len - k % len; i > 1; i--)

head = head.next;

copyHead = head.next;

head.next = null;

return copyHead;

}

}