数据结构之链表

链表基本运算实现以及快慢指针应用

单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

单链表中的节点应该具有两个属性：val和next。

val是当前节点的值
next 是指向下一个节点的指针/引用
如果要使用双向链表，则还需要一个属性prev以指示链表中的上一个节点。

定义：

// Definition for singly-linked list.
struct SinglyListNode {
    int val;
    SinglyListNode *next;
    SinglyListNode(int x) : val(x), next(NULL) {}
};

函数功能

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

C++函数实现

class MyLinkedList {
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
		    size = 0;
		    head = nullptr;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        if(index >= size || index < 0 || head == nullptr) {
            return -1;
        }
        SinglyListNode *temp = head;  //从第一个节点开始
        for (int i = 0;i < index; ++i) {
          temp = temp->next;  //遍历查找
        }
        return temp->val; //返回该index的val值
    }
    
    /** 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. */
    void addAtHead(int val) {
        SinglyListNode *temp = new SinglyListNode(val);  //new一个val值的结点
        temp->next = head; //加在链表第一个元素之前
        temp = nullptr;
        size++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
      if (size == 0) {
        head = new SinglyListNode(val);  //新建第一个结点
        ++size;
      }
      SinglyListNode *find = head;
      while (find->next != nullptr) {
        find = find->next;  //遍历到最后一个结点
      }

      SinglyListNode *temp = new SinglyListNode(val);
      find->next = temp;  //最后一个节点的指针指向需要添加的这个元素
      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. */
    void addAtIndex(int index, int val) {
      if (index > size) return;

      if (index <= 0) {
        addAtHead(val);  //添加为第一个元素之前
        return;
      }

      SinglyListNode *pr = head;
      for (int i = 0;i < index-1; ++i) {
        pr = pr->next;
      }
      
      SinglyListNode *cur = new SinglyListNode(val);
      cur->next = pr->next;  //插入到查找到的index前面
      pr->next = cur;
      size++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if (index > size) return;
        
        if (index < 0)    return;

        if (index == 0) {
          head = head->next;
          size--;
          return;
        }

        SinglyListNode *del = head;
        for (int i = 0;i < index-1; ++i) {
          del = del->next;
        }
        del->next = del->next->next;
        size--;
    }

    /*  打印链表 */
    void print() {
      if (size == 0) {
        cout << "empty" <<endl;
      }

      SinglyListNode *pr = head;
      for(int i=0; i<size; ++i) {
        cout << "Node " << i << " : " << pr->val <<endl;
        pr = pr->next;
      }
    }

	~MyLinkedList() {
		size = 0;
		head = nullptr;	
	}

private:
      struct SinglyListNode {
        int val;
        SinglyListNode *next;
        SinglyListNode(int x) : val(x), next(nullptr) {}
      };
      int size;
      SinglyListNode* head;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */
 //new对象，调用方法
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

C++的i++和++i

i++ ：先引用后增加，先在i所在的表达式中使用i的当前值，后让i加1

++i ：先增加后引用，让i先加1，然后在i所在的表达式中使用i的新值

即：

++i是将i的值先+1，然后返回i的值
i++是先将i的值存到寄存器里，然后执行i+1，然后返回寄存器里的值。

链表双指针模板（快慢指针java&cpp）

快慢指针可用于环形链表、相交链表的查询等运算

注意以下点：

在调用 next 字段之前，始终检查节点是否为空。获取空节点的下一个节点将导致空指针错误。例如，在我们运行fast = fast.next.next之前，需要检查fast和fast.next不为空
仔细定义循环的结束条件

C++语言版

// Initialize slow & fast pointers
ListNode* slow = head;
ListNode* fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow && fast && fast->next) {
    slow = slow->next;          // move slow pointer one step each time
    fast = fast->next->next;    // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem

Java语言：

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem

在环形链表的查找循环中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步：

如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度

显然，M <= N。所以我们将循环运行N次。该算法的时间复杂度总共为O(N)

单链表

函数功能

C++函数实现

C++的i++和++i

链表双指针模板（快慢指针java&cpp）

参考