FilesExpand file tree

 master

/

DesignLinkedList_707.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

91 lines (79 loc) · 2.63 KB

 master

/

DesignLinkedList_707.java

Copy path

Top

File metadata and controls

• Code
• Blame

91 lines (79 loc) · 2.63 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

package Lists;

/**

* 实现一个链表

*/

public class DesignLinkedList_707 {

private Node head = null;

private int size = 0;

private static class Node {

private int val;

private Node next;

public Node (int v, Node next) {

val = v;

this.next = next;

}

public int getVal() {return val;}

public void setVal(int v) {this.val = v;}

public void setNext(Node next) {

this.next = next;

}

public Node getNext() {return this.next;}

}

/** Initialize your data structure here. */

public DesignLinkedList_707() {

}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */

public int get(int index) {

Node node = getNode(index);

return node == null ? -1 : node.getVal();

}

private Node getNode(int index) {

if (index < 0 || index >= size) return null;

Node visit = head;

while(index != 0) {

visit = visit.next;

index--;

}

return visit;

}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */

public void addAtHead(int val) {

Node cur = new Node(val, head);

head = cur;

size++;

}

/** Append a node of value val to the last element of the linked list. */

public void addAtTail(int val) {

Node trav = head;

while(trav.next != null) {

trav = trav.next;

}

Node cur = new Node(val, null);

trav.next = cur;

size++;

}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */

public void addAtIndex(int index, int val) {

if (index < 0 || index > size) return;

if (index == 0) addAtHead(val);

else if (index == size) addAtTail(val);

else {

Node prev = getNode(index-1);

Node cur = new Node(val, prev.next);

prev.next = cur;

size++;

}

}

/** Delete the index-th node in the linked list, if the index is valid. */

public void deleteAtIndex(int index) {

if (index < 0 || index >= size) return;

if (index == 0) {

head = head.next;

} else {

Node prev = getNode(index-1);

Node after = prev.next.next;

prev.next = after;

}

size--;

}

}