FilesExpand file tree

master

/

test22.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

70 lines (65 loc) · 1.93 KB

master

/

test22.java

Copy path

Top

File metadata and controls

• Code
• Blame

70 lines (65 loc) · 1.93 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

package byteDance;

/**

* Created by lizeyang on 2020/5/14.

* 反转链表

*/

public class test22 {

//原地反转链表,O(n)

public static ListNode reverseList(ListNode root) {

if (root == null || root.next == null) {

return root;

}

ListNode pre = null;

ListNode index = root;

ListNode last = index.next;

while (last != null) {

index.next = pre;

pre = index;

index = last;

last = last.next;

}

index.next = pre;

return index;

}

//升级->每k个反转一下,O(n)

public static ListNode reverseListK(ListNode root, int k) {

if (root == null || root.next == null) {

return root;

}

ListNode dummy = new ListNode(0), pre = dummy, cur = root, last;

dummy.next = root;

int length = 0;

while (root != null) {

length++;

root = root.next;

}

for (int i = 0; i < length / k; i++) {

for (int j = 0; j < k - 1; j++) {

last = cur.next;

cur.next = last.next;

last.next = pre.next;

pre.next = last;

}

pre = cur;

cur = pre.next;

}

return dummy.next;

}

public static void main(String[] args) {

ListNode root = new ListNode(1);

root.next = new ListNode(2);

root.next.next = new ListNode(4);

root.next.next.next = new ListNode(5);

root.next.next.next.next = new ListNode(6);

root.next.next.next.next.next = new ListNode(8);

root.next.next.next.next.next.next = new ListNode(9);

//反转链表

// ListNode res = reverseList(root);

//每k个反转链表

ListNode res = reverseListK(root, 3);

while (res != null) {

System.out.print(res.val + " ");

res = res.next;

}

}

}