移除链表元素

题目链接

https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

思路

链表用虚拟节点会容易操作很多。

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

设计链表

题目链接

https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

思路

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;
    }
    int i = 0;
    ListNode node = head;
    while(i++ <= index) {
        node = node.next;
    }
    return node.val;
}

public void addAtHead(int val) {
    addAtIndex(0, val);
}

public void addAtTail(int val) {
    addAtIndex(size, val);
}

public void addAtIndex(int index, int val) {
    if (index > size) {
        return;
    }
    int i = 0;
    ListNode cur = head;
    while(i++ < index) {
        cur = cur.next;
    }
    ListNode node = new ListNode(val);
    size++;
    node.next = cur.next;
    cur.next = node;
}

public void deleteAtIndex(int index) {
    if(index<0 || index >= size) {
        return;
    }
    size--;
    ListNode cur = head;
    int i = 0;
    while(i++ < index) {
        cur = cur.next;
    }
    cur.next = cur.next.next;
}
}

反转链表

题目链接

https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

思路

头插法，使用虚拟节点实现

public ListNode reverseList(ListNode head) {
    if(head == null) {
        return null;
    }
    ListNode dummy = new ListNode(-1);
    ListNode cur = head;
    while(cur != null) {
        ListNode temp = cur.next;
        cur.next = dummy.next; 
        dummy.next = cur;
        cur = temp;
    }
    return dummy.next;
}

 // 双指针

 ListNode pre = null, cur = head;
while(cur != null) {
   ListNode tmp = cur.next;
   cur.next = pre;
   pre = cur;
   cur = tmp;
}
return pre;

 //递归
 public ListNode reverseList(ListNode head) {
  return reverse(null, head);
}

public ListNode reverse(ListNode pre, ListNode head) {
  if (head == null) {
    return pre;
  }
  ListNode tmp = head.next;
  head.next = pre;
  return reverse(head, tmp);
}

 //栈
 if (head == null) {
      return null;
    }
    Stack<ListNode> stack = new Stack();
    while(head != null) {
      stack.push(head);
      head = head.next;

    }
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while(!stack.isEmpty()) {
      ListNode tmp = stack.pop();
      cur.next = tmp;
      cur = tmp;
    }
    cur.next = null;
    return dummy.next;