Leetcode-707：设计链表（单链表、双链表）_你可以选择使用单链表或者双链表

题目描述：

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3
1
2
3
4
5
6
7

分析：
题目描述中，在设计链表的时候，可以考虑单链表和双链表两种情况，而单链表和双链表唯一的区别就是双链表比单链表在节点上多了一个指向前的引用。因此，我们在这分两种情况做这个题。

思路一：单链表

• get(index)：获取索引为index的节点，思路很简单，只需要循环index次然后拿到下标为index的节点即可。
• addAtHead(val)：只需要将当前链表的头指向新生成的节点（val），将原有的链表接在新的头节点后面即可。
• addAtTail(val)：直接遍历节点到最后一个，将新生成的节点(val)接在原有链表最后面。
• addAtIndex(index,val)：遍历index-1次，将新节点插入。注意:1、index是否有效。2、链表是否为空（为空即是头插）
• deleteAtIndex(index)：遍历index-1次，删除下一个节点。注意：1、index的取值是否有效。2、删除的是否为头节点（头节点直接让头引用向后移）

代码：

class ListNode{
    public int val;
    public ListNode next;
    public ListNode(int val)
    {
        this.val=val;
        this.next=null;
    }
}

class MyLinkedList {
    
    private int size;
    public ListNode head;
    /** Initialize your data structure here. */
    public MyLinkedList() {
        this.size=0;
        this.head=null;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        ListNode cur=head;
        while(cur!=null)
        {
            if(index==0)
            {
                return cur.val;
            }
            index--;
            cur=cur.next;
        }
        return -1;
    }
    
    /** 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) {
        ListNode cur= new ListNode(val);
        cur.next=head;
        head=cur;
        this.size++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if(size==0)
        {
            head=new ListNode(val);
            return;
        }
        ListNode cur=head;
        while(cur.next!=null)
        {
            cur=cur.next;
        }
        cur.next=new ListNode(val);
        this.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)
        {
            addAtHead(val);
            return;
        }
         int num=0;
         ListNode cur=head;
        while(cur!=null)
        {            
            if(num==index-1)
            {
                ListNode Ttmp=cur.next!=null?cur.next:null;
                cur.next=new ListNode(val);
                cur.next.next=Ttmp;
                size++;
               return;
            }

            num++;
            cur=cur.next;
        }
        return ;
    }
    
    /** 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;
            size--;
            return;
        }
        ListNode cur=head;
        size--;
        for(int i=0;i<index-1;i++)
        {
           cur=cur.next;
        }
        cur.next=cur.next.next;
    }
}
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
101
102
103
104
105
106

思路二：双向链表

对于双向链表，他唯一不同的就是多了一个指向前的引用prev，在实现各个方法的过程中，一定要注意不要忘记改变prev的指向，还有就是当改变prev指向的同时尤其得判断一下这个节点是否为空，为空的话就不能改变他的prev指向了。

代码：

class ListNode{
    public int val;
    public ListNode next;
    public ListNode prev;
    public ListNode(int val)
    {
        this.val=val;
        this.next=null;
        this.prev=null;
    }
}

class MyLinkedList {
    
    private int size;
    public ListNode head;
    /** Initialize your data structure here. */
    public MyLinkedList() {
        this.size=0;
        this.head=null;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        ListNode cur=head;
        while(cur!=null)
        {
            if(index==0)
            {
                return cur.val;
            }
            index--;
            cur=cur.next;
        }
        return -1;
    }
    
    /** 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) {
        ListNode cur= new ListNode(val);
        cur.next=head;
        cur.prev=null;
        head=cur;
        this.size++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if(size==0)
        {
            head=new ListNode(val);
            return;
        }
        ListNode cur=head;
        while(cur.next!=null)
        {
            cur=cur.next;
        }
        cur.next=new ListNode(val);
        cur.next.prev=cur;
        this.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)
        {
            addAtHead(val);
            return;
        }
       
         int num=0;
         ListNode cur=head;
        while(cur!=null)
        {            
            if(num==index-1)
            {
                ListNode Ttmp=cur.next!=null?cur.next:null;
                cur.next=new ListNode(val);
                cur.next.next=Ttmp;
                cur.next.prev=cur;
                if(Ttmp!=null)
                Ttmp.prev=cur.next;
                size++;
               return;
            }

            num++;
            cur=cur.next;
        }
        return ;
    }
    
    /** 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;
         
            size--;
            return;
        }
        ListNode cur=head;
        size--;
        for(int i=0;i<index-1;i++)
        {
           cur=cur.next;
        }
        cur.next=cur.next.next;
        if(cur.next!=null)
        cur.next.prev=cur;
    }
}

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118