设计链表

https://leetcode-cn.com/problems/design-linked-list/

  1. class MyLinkedList {
  3.     private Node first;
  4.     private Node last;
  5.     private int n = 0;
  7.     class Node{
  8.         Node next = null;
  9.         int val;
  10.     }
  12.     public MyLinkedList() {
  14.     }
  16.     /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  17.     public int get(int index) {
  18.         if(index > n - 1) //超出范围返回-1
  19.             return -1;
  20.         else{
  21.             Node r = first;
  22.             while(index > 0){
  23.                 r = r.next;
  24.                 index--;
  25.             }
  26.             return r.val;
  27.         }
  28.     }
  30.     /** 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. */
  31.     public void addAtHead(int val) {
  32.         Node temp = new Node();
  33.         temp.val = val;
  34.         if(first == null){ //若链表为空
  35.             first = last = temp;
  36.         }
  37.         else{
  38.             temp.next = first;
  39.             first = temp;
  40.         }
  41.         n++;
  42.     }
  44.     /** Append a node of value val to the last element of the linked list. */
  45.     public void addAtTail(int val) {
  46.         Node temp = new Node();
  47.         temp.val = val;
  48.         if(last == null){ //若链表为空
  49.             first = last = temp;
  50.         }
  51.         else{
  52.             last.next = temp;
  53.             last = temp;
  54.         }
  55.         n++;
  56.     }
  58.     /** 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. */
  59.     public void addAtIndex(int index, int val) {
  60.         if(index <= n){ //插入位置合法
  61.             if(index == 0){
  62.                 addAtHead(val);
  63.                 return;
  64.             }
  65.             Node pre = first;
  66.             while(index > 1){
  67.                 pre = pre.next;
  68.                 index--;
  69.             }
  70.             Node temp = new Node();
  71.             temp.val = val;
  72.             temp.next = pre.next;
  73.             pre.next = temp;
  74.             if(pre == last) //若插入到最后一个节点，移动last
  75.                 last = temp;
  76.             n++;
  77.         }
  78.     }
  80.     /** Delete the index-th node in the linked list, if the index is valid. */
  81.     public void deleteAtIndex(int index) {
  82.         if(index + 1 <= n){
  83.             if(index == 0){
  84.                 first = first.next;
  85.                 return;
  86.             }
  87.             Node pre = first;
  88.             while(index > 1){
  89.                 pre = pre.next;
  90.                 index--;
  91.             }
  92.             Node del = pre.next;
  93.             pre.next = del.next;
  94.             if(del == last) //若删除的最后一个节点，移动last
  95.                 last = pre;
  96.             n--;
  97.         }
  98.     }
  99. }

双指针

环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

  1. bool hasCycle(struct ListNode *head) {
  2.     struct ListNode * fast;
  3.     struct ListNode * slow;
  4.     fast = slow = head;
  5.     while(fast){
  6.         if(fast->next){
  7.             fast = fast->next->next;
  8.             slow = slow->next;
  9.             if(fast == slow)
  10.                 return true;
  11.         }
  12.         else return false; 
  13.     }
  14.     return false;
  15. }
  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         ListNode slow = head;
  4.         ListNode fast = head;
  5.         int i;
  6.         if(head == null)
  7.             return false;
  8.         //注意一开始快慢指针是相等的，需要排除
  9.         for(i = 0; !(fast == slow && i != 0); i++){
  10.             slow = slow.next;
  11.             fast = fast.next;
  12.             if(fast != null && fast.next != null)
  13.                 fast = fast.next;
  14.             else return false;
  15.         }
  16.         return true;
  17.     }
  18. }

环形链表 II

https://leetcode-cn.com/problems/linked-list-cycle-ii/

  1. struct ListNode *detectCycle(struct ListNode *head) {
  2.     struct ListNode * fast;
  3.     struct ListNode * slow;
  4.     fast = slow = head;
  5.     while(fast){
  6.         if(fast->next){
  7.             fast = fast->next->next;
  8.             slow = slow->next;
  9.             if(fast == slow){
  10.                 struct ListNode * p = head;
  11.                 while(p != slow){
  12.                     slow = slow->next;
  13.                     p = p->next;
  14.                 }
  15.                 return p;
  16.             }
  17.         }
  18.         else return false;
  19.     }
  20.     return false;
  21. }
  1. public class Solution {
  2.     public ListNode detectCycle(ListNode head) {
  3.         ListNode slow = head;
  4.         ListNode fast = head;
  5.         int i;
  6.         if(head == null)
  7.             return null;
  8.         //注意一开始快慢指针是相等的，需要排除
  9.         for(i = 0; !(fast == slow && i != 0); i++){
  10.             slow = slow.next;
  11.             fast = fast.next;
  12.             if(fast != null && fast.next != null)
  13.                 fast = fast.next;
  14.             else return null;
  15.         }
  16.         ListNode temp = head;
  17.         //当slow与fast相遇时，再使用一个指针ptr指向链表头部，它和 slow 每次向后移动一个位置，最终会在入环点相遇，具体公式推导见原网页
  18.         while(temp != slow){
  19.             slow = slow.next;
  20.             temp = temp.next;
  21.         }
  22.         return temp;
  23.     }
  24. }

相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     struct ListNode *a = headA;
  3.     struct ListNode *b = headB;
  4.     bool flagA = false;
  5.     bool flagB = false;
  6.     while(a && b){
  7.         if(a == b){
  8.             return a;
  9.         }
  10.         a = a->next;
  11.         b = b->next;
  12.         if(!a && !flagA){
  13.             a = headB;
  14.             flagA = true;
  15.         }
  16.         if(!b && !flagB){
  17.             b = headA;
  18.             flagB = true;
  19.         }
  20.     }
  21.     return false;
  22. }
  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         ListNode a = headA;
  4.         ListNode b = headB;
  5.         if(headA == null || headB == null)
  6.             return null;
  7.         while(a != b){
  8.             a = a.next;
  9.             b = b.next;
  10.             if(a == b && b == null)
  11.                 return null;
  12.             if(a == null)
  13.                 a = headB;
  14.             if(b == null)
  15.                 b = headA;
  16.         }
  17.         return a;
  18.     }
  19. }

删除链表的倒数第 N 个结点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

  1. struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
  2.     struct ListNode* p = head;
  3.     struct ListNode* q = head;
  4.     n++;
  5.     while(n != 0){
  6.         if(p){
  7.             p = p->next;
  8.             n--;
  9.         }
  10.         else{
  11.             //删除头结点
  12.             head = head->next;
  13.             return head;
  14.         }
  15.     }
  16.     while(p){
  17.         p = p->next;
  18.         q = q->next;
  19.     }
  20.     q->next = q->next->next;
  21.     return head;
  22. }
  1. class Solution {
  2.     public ListNode removeNthFromEnd(ListNode head, int n) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         ListNode pre = null;
  6.         while(n > 1){
  7.             fast = fast.next;
  8.             n--;
  9.         }
  10.         while(fast.next != null){
  11.             fast = fast.next;
  12.             pre = slow;
  13.             slow = slow.next;
  14.         }
  15.         //删除头节点
  16.         if(pre == null)
  17.             return head.next;
  18.         //删除尾节点
  19.         if(slow == fast)
  20.             pre.next = null;
  21.         else pre.next = slow.next;
  22.         return head;
  23.     }
  24. }

经典问题

反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

  1. struct ListNode* reverseList(struct ListNode* head){
  2.     struct ListNode* pre = NULL;
  3.     struct ListNode* cur = head;
  4.     while(cur){
  5.         struct ListNode* next = cur->next;
  6.         cur->next = pre;
  7.         pre = cur;
  8.         cur = next;
  9.     }
  10.     return pre;
  11. }
  1. //递归
  2. //反转以head为头结点的链表，返回反转后的头结点
  3. struct ListNode* reverseList(struct ListNode* head){
  4.     if(head == NULL || head->next == NULL)
  5.         return head;
  6.     struct ListNode* rev = reverseList(head->next);
  7.     head->next->next = head;
  8.     head->next = NULL;
  9.     return rev;
  10. }
  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         ListNode pre = null;
  4.         ListNode cur = head;
  5.         while(cur != null){
  6.             ListNode next = cur.next;
  7.             cur.next = pre;
  8.             pre = cur;
  9.             cur = next;
  10.         }
  11.         return pre;
  12.     }
  13. }
  1. //递归
  2. class Solution {
  3.     public ListNode reverseList(ListNode head) {
  4.         if(head == null || head.next == null){
  5.             return head;
  6.         }
  7.         ListNode rev = reverseList(head.next);
  8.         head.next.next = head;
  9.         head.next = null;
  10.         return rev;
  11.     }
  12. }

移除链表元素

https://leetcode-cn.com/problems/remove-linked-list-elements/

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;

    while(cur){
        if(cur->val == val){
            //删除头结点
            if(pre == NULL){
                cur = cur->next;
                head = head->next;
                continue;
            }
            pre->next = cur->next;
        }
        else {
            //没有删除， pre 向前移动
            pre = cur;
        }
        cur = cur->next;
    }
    return head;
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode start = new ListNode(-1);
        start.next = head;
        ListNode pre = start;
        ListNode cur = head;
        while(cur != null){
            if(cur.val == val)
                pre.next = cur.next;
            else 
                pre = pre.next;
            cur = cur.next;
        }
        //注意不能直接返回head
        return start.next;
    }
}