# ListNode definition
public class ListNode {
    // 结点的值
    int val;
    // 下一个结点
    ListNode next;
    // 节点的构造函数(无参)
    public ListNode() {
    }
    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }
    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

No.1

题目

移除链表元素

思路

• 设置dummyHead以相同方式处理以下情况
  • 待删除节点处于头节点
  • 待删除节点处于链表中间
• 遍历链表，遇到目标就 pre.next = cur.next ，复杂度O(n)

代码

// 设置dummyHead.next=head  
ListNode dummyHead = new ListNode(0, head);  
// 从head开始遍历  
ListNode pre = dummyHead;  
ListNode cur = head;  
// 空数组，直接返回null  
if (head == null)  
    return null;  
// 外层循环遍历ListNode中的val值  
while (cur != null) {  
    if (cur.val == val)  
        pre.next = cur.next;  
    elsepre = cur;  
    cur = cur.next;  
}  
return dummyHead.next;

No.2

题目

设计链表

思路

• 厘清每个方法要求实现的功能和边界条件
• addAtHead(int val) 和 addAtTail(int val)其实都是addAtIndex(int index, int val)的特殊情况
• add和delete的时候同步nodeNum

代码

class MyLinkedList {  
    private int nodeNum;  
    private ListNode dummyHead;  
    public MyLinkedList() {  
        dummyHead = new ListNode();  
        nodeNum = 0;  
    }  
    public int get(int index) {  
        if (index < 0 || index >= nodeNum)  
            return -1;  
        ListNode cur = dummyHead.next;  
        int count = 0;  
        // 只要不满足，就一直往count++的方向找  
        while (count < index) {  
            cur = cur.next;  
            count++;  
        }  
        // 退出while，count == index  
        return cur.val;  
    }  
    public void addAtHead(int val) {  
        addAtIndex(0, val);  
    }  
    public void addAtTail(int val) {  
        addAtIndex(nodeNum, val);  
    }  
    public void addAtIndex(int index, int val) {  
        if (index >= 0 && index <= nodeNum) { // 把index==nodeNum的情况考虑进来  
            ListNode pre = dummyHead;  
            ListNode cur = pre.next;  
            int count = 0;  
            while (count < index) {  
                pre = cur;  
                cur = cur.next;  
                count++;  
            }  
            ListNode newNode = new ListNode(val);  
            nodeNum++;  
            pre.next = newNode;  
            newNode.next = cur;  
        }  
    }  
    public void deleteAtIndex(int index) {  
        if (index >= 0 && index < nodeNum) { // index==nodeNum感觉越界了，就没有包括进来  
            ListNode pre = dummyHead;  
            ListNode cur = pre.next;  
            int count = 0;  
            // 只要不满足，就一直往count++的方向找  
            while (count < index) {  
                pre = cur;  
                cur = cur.next;  
                count++;  
            }  
            // 退出while，count == index  
            pre.next = cur.next;  
            nodeNum--;  
        }  
    }  
}

No.3

题目

反转链表

思路

• 双指针pre和cur，一边遍历一遍反转
• 提前存储cur.next值，便于cur.next=pre后找到原来下一个节点的位置
• 注意pre=cur和cur=tmp操作的顺序

代码

public ListNode reverseList(ListNode head) {  
    ListNode pre = null, cur = head;  
    while (cur != null) {  
        // 先存下cur.next  
        ListNode tmp = cur.next;  
        // 反转指向：cur指向pre  
        cur.next = pre;  
        // 更新pre和cur指向，为下次操作准备：  
        pre = cur;  
        cur = tmp;  
    }  
    return pre;  
}