算法-有序链表（一）

1.合并两个有序链表

• 基础代码实现

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   * int val;
   * ListNode next;
   * ListNode() {}
   * ListNode(int val) { this.val = val; }
   * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
  class Solution {
      public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
          //定义哨兵头结点，便于返回数据
          ListNode dummy = new ListNode(0);
          //定义当前节点，便于操控索引前进
          ListNode current = dummy;
          while (list1 != null && list2 != null) {
              if (list1.val < list2.val) {
                  //让较小的值插入到当前节点的下一个节点
                  current.next = list1;
                  //让当前 current 指向的节点移动到下一个节点
                  list1 = list1.next;
              } else {
                  current.next = list2;
                  list2 = list2.next;
              }
              //向下移动主节点
              current = current.next;
          }
          //如果其中一个节点遍历完毕或为空，就让另一个节点剩下的元素插入到 current 的下一个节点
          if (list1 == null) {
              current.next = list2;
              return dummy.next;
          }
          if (list2 == null) {
              current.next = list1;
              return dummy.next;
          }
          return dummy.next;
      }

2.删除排序链表中的重复元素

• 基础代码实现

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   * int val;
   * ListNode next;
   * ListNode() {}
   * ListNode(int val) { this.val = val; }
   * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   * }
   */
  class Solution {
      public ListNode deleteDuplicates(ListNode head) {
          // 定义当前指针
          ListNode cur = head;
          if(head == null){
              return null;
          }
          while (cur.next != null) {
              // 如果当前值和下一个值相等，那就直接指向下下一个值（删除下一个值）
              if (cur.val == cur.next.val) {
                  cur.next = cur.next.next;
              // 否则前移动
              }else{
                  cur = cur.next;
              }
          }
          return head;
      }
  }