链表数据结构

链表数据结构

1· 删除链表的节点在O（1）时间内(18 剑指offer )

• 解题思路 : 可以通过用下一个节点覆盖要删除的前一个节点，达到O（1）的时间
• 在链表中需要考虑到：
  1. 要删除的节点不是尾节点的 O（1）情况 ；
  2. 链表只有一个节点 ；
  3. 链表有多个节点，要删除的节点是尾节点；

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode toBeDeleted, ListNode root) {
       /* 要删除的链表不是尾节点 的O（1）情况*/
      if(toBeDeleted.next != null) {
          toBeDeleted.val = toBeDeleted.next.val;
          toBeDeleted.next = toBeDeleted.next.next;
      }
      else if( toBeDeleted == root){
    
          root = null;
      }
      else{ /* 要删除链表的尾部*/
          ListNode ptr = root;
          while( ptr.next != toBeDeleted ){
                ptr = ptr.next;
          }
           ptr.next = null;
      }
    }
}

2· 删除链表中重复的节点 (18 剑指offer )

• 这里会使用到dummy node因为有可能会删除链表的头部，所以需要dummy node
  -也会用到双指针 指向要删除的节点串的 前一个node，和要删除的节点串的后一个node。当 前一个node 和 后一个node 的中间始终相隔一个node， 就继续遍历， 反之就进行删除操作。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplication(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode ptr = dummy; /*从dummy node 这里开始遍历，因为root 也是有可能被删的*/
        /* 这里不写*/
        while(ptr.next != null){
             ListNode pNext = ptr.next;
              while(pNext != null && ptr.next.val == pNext.val)
                    pNext ++;
              if( ptr.next.next == pNext)
                      ptr = ptr.next;
              else{
                  ptr.next = pNext;
              }      
         }/* while*/
     return dummy.next;
    }
}