代码随想录算法训练营第三天（LeetCode203.移除链表元素；LeetCode707.设计链表；LeetCode206.反转链表）

LeetCode 203. 移除链表元素

题目链接：LeetCode203.移除链表元素题目链接

思路

这道题目主要考察的是移除一个链表当中的元素，我们可以先在给定的链表前面加一个虚拟头结点，这样我们对给定链表头结点的操作和给定链表其余结点的操作就会变得相同。

代码

class Solution {
    public ListNode removeElements(ListNode head, int val) {
         ListNode dummy=new ListNode();
         dummy.next=head;
         ListNode cur=dummy;
         while(cur.next!=null)
         {
            if(cur.next.val==val)
            {
                cur.next=cur.next.next;
            }
            else
            {
                cur=cur.next;
            }
         }
         return dummy.next;
    }
}

LeetCode 707. 设计链表

题目链接：LeetCode707.设计链表题目链接

思路

这道题目主要考察的是链表的基础操作。

代码

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){
        this.val=val;
    }
}
class MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        size=0;
        head=new ListNode(0);
    }
    
    public int get(int index) {
        if(index<0||index>=size)
            return -1;
        ListNode cur=head;
        for(int i=0;i<=index;i++)
        {
            cur=cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        ListNode newhead=new ListNode(val);
        newhead.next=head.next;
        head.next=newhead;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode cur=head;
        while(cur.next!=null)
            cur=cur.next;
        ListNode newtail=new ListNode(val);
        cur.next=newtail;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size)
            return;
        if(index<0)
            index=0;
        ListNode cur=head;
        for(int i=0;i<index;i++)
            cur=cur.next;
        ListNode node=new ListNode(val);
        node.next=cur.next;
        cur.next=node;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index<0||index>=size)
            return;
        ListNode cur=head;
        for(int i=0;i<index;i++)
            cur=cur.next;
        cur.next=cur.next.next;
        size--;
    }
}

LeetCode 206. 反转链表

题目链接：LeetCode206.反转链表题目链接

思路

在这道题目中其实就是给定我们一个链表，让我们将这个链表反转。我们可以采用双指针的做法来解决这个问题，一个 pre 指针指向 null，一个 cur 指针指向给定链表的头节点，一个 temp 指针指向 cur 指针的下一个指针（因为 cur 指针的下一步操作就是指向改为 pre，所以原先的下一个链表节点需要进行存储），cur 的指向改为 pre。然后更新 pre 为 cur，更新 cur 为 temp。直到 cur 指向 null，pre 就指向了给定链表的尾节点，同时，这个链表的指针也被我们全部反转了，所以返回 pre 就可以了。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre=null;
        ListNode cur=head;
        ListNode temp;
        while(cur!=null)
        {
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}