leetcode链表

---

data: 2020-8-3
tags:
categories:

• 数据结构与算法

---

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

• 两次遍历,单指针，第一遍测出链表总长度，第二遍遍历到要删除的节点位置

    public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       int length = 0;
       ListNode first = head;
       while(first != null){ //得出链表长度
           length++;   
           first=first.next;
       }
      length -= n;   //链表长度减去n
      first = dummy;
      while(length>0){//遍历到刚好要删除的节点
          length--;
          first = first.next;
      }
      first.next = first.next.next;//删除节点
      return dummy.next; //返回头节点
    }
  

• 一次遍历，双指针，两个指针保持n的距离，遍历到末尾即可

    ListNode pre = new ListNode(0);
      pre.next = head;
      ListNode end = pre;
      ListNode start = pre;
      int length = 0;
      while(n>0){  //先让end，先走n步
          n--;
          end = end.next;
      }
      while(end.next != null){ //一起走，走到末尾
          start = start.next;
          end = end.next;
      }
      start.next = start.next.next;//删除节点
      return pre.next;
  

• 递归遍历

    /**
      递归方法
      */  
      int i;
      public ListNode removeNthFromEnd(ListNode head, int n) {    
          if (head == null) {
              i = 0;
              return null;
          }
  
          head.next = removeNthFromEnd(head.next, n);
          i++;  // 归的过程中会按倒序依次增加序号
          if (i == n) return head.next;  
          // 此时的节点为待删除节点，返回其next节点跨过待删除节点，达到删除节点的目的
          return head;  // 其他情况下正常返回本节点
      }
  

23 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

• 利用两两合并的，利用遍历将k个逐渐合并

  class Solution {
      public ListNode mergeKLists(ListNode[] lists) {
          ListNode res = null;
          for (ListNode list: lists) {
              res = merge2Lis  ts(res, list);
          }
          return res;
      }
  }
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //合并两个
          ListNode l3 = new ListNode(0);
          ListNode head = l3;
          while(l1 != null && l2!=null){
              if(l1.val > l2.val){
                  l3.next = l2;
                  l3 = l3.next;
                  l2 = l2.next;
              }
              else{
                  l3.next = l1;
                  l3 = l3.next;
                  l1 = l1.next;
              }
          }
            if(l1 == null){
                  l3.next = l2;
              }
              if(l2 == null){
                  l3.next = l1;
              }
          return head.next;
      }
  

• 同样利用两两合并，同时利用分治算法

  

public ListNode mergeKLists(ListNode[] lists) {
		if(lists==null || lists.length==0) {
			return null;
		}
		return helper(lists,0,lists.length-1);
	}
	
	//通过mid将数组一分为二，并不断缩小规模，当规模为1时返回并开始合并
	//通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程
	private ListNode helper(ListNode[] lists, int begin, int end) {
		if(begin==end) {//递归到底了
			return lists[begin];
		}
		int mid = begin+(end-begin)/2;
		ListNode left = helper(lists,begin,mid);//得到左边部分
		ListNode right = helper(lists,mid+1,end);//得到右边部分
		return merge(left,right);//合并左右，并返回给上一级
	}
	

• 利用队列排序

  

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

• 迭代

  class Solution {
      public ListNode swapPairs(ListNode head) {
          ListNode dummy = new ListNode(-1);
          dummy.next = head;
          ListNode prevNode = dummy;
          while((head != null) && (head.next != null)){
              ListNode firstNode = head;  //拿到第一个节点
              ListNode secondNode = head.next;//拿到第二个节点
  
              prevNode.next = secondNode;//将第二个节点置前
              firstNode.next = secondNode.next;  //交换位置
              secondNode.next = firstNode;
  
              prevNode = firstNode;//指向第二个位置
              head = firstNode.next;//移动两格
          }
          return dummy.next;
      }
      }
  

• 递归

     public ListNode swapPairs(ListNode head) {
          // If the list has no node or has only one node left.
          if ((head == null) || (head.next == null)) {//递归到底
              return head;    
          }
  
          // Nodes to be swapped
          ListNode firstNode = head;//第一个节点
          ListNode secondNode = head.next;//第二个节点
  
          // Swapping 
          firstNode.next  = swapPairs(secondNode.next);
          secondNode.next = firstNode;
  
          // Now the head is the second node
          return secondNode;
     }
  

61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL

向右旋转 4 步: 2->0->1->NULL

• 先遍历总长度length
• 判断k大于length长度，求余
• 将倒数K位拼接到队头

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null ){
            return null;
        }
        if(k <= 0){
            return head;
        }
  
       int length = 0;
        ListNode first = head;
       while(first != null){ //得出链表长度
          length++;   
          first=first.next;
      }  
    
     if(k>=length){//k比链表长度大
          k = k%length;
     }
     if(k == 0){  //k为length的倍数，恰好不用旋转
          return head; 
      }
    int flag = length - k -1; //倒数的K+1
    ListNode end = head; //指向链表头部
     while(flag>0){
        end = end.next;
        flag--;
    }
    ListNode newHead =  end.next;
    end.next  = null;//末尾指向空
  
    first = newHead;
    while(first.next != null){ //遍历到末尾
        first = first.next;    
    }
    first.next = head; //将末尾拼上队头
    return newHead;
    }

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

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

• class Solution {
      public ListNode deleteDuplicates(ListNode head) {
      ListNode current = head;
      while (current != null && current.next != null) {
          if (current.next.val == current.val) {
              current.next = current.next.next;//跳过
          } else { 
              current = current.next;//正常遍历
          }
      }
      return head;
  
      }
  }
  

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

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
      if(head == null) return null;
      ListNode dummy = new ListNode(-1000);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy.next;
        while (fast != null) {//遍历数组
            while (fast.next != null && fast.val == fast.next.val) 
               fast = fast.next; //跳到相同数字的最后一个
            if (slow.next == fast) //无相同数字情况下
               slow = slow.next; 
            else   //相同数字，要跳过
                slow.next = fast.next; //跳到下一个
            fast = fast.next;
        }
        return dummy.next; 
    }   
}

86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

class Solution {
    public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
		if(head==null || head.next==null) {
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);
		head.next.next = head;//设置转向
		//防止链表循环，断开转向后的next
		head.next = null;
		//每层递归函数都返回cur，也就是最后一个节点
		return cur;
    }
}

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
 // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
    }
    ListNode successor = null; // 后驱节点
    public ListNode reverseN(ListNode head, int n){
        if (n == 1) { 
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    } 
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
        
    }
}

142. 环形链表 II

• 双指针，快慢指针，两倍速

• 第一次相遇，快指针多走了n个环的长度，则慢指针总共走了n个环长度（两倍速）

• 把快指针指向队头，一倍速

• 第二次相遇，快指针走了距离a，慢指针则为a+nb，一定相遇了

• a为所求

  public class Solution {
      public ListNode detectCycle(ListNode head) {
             ListNode fast = head, slow = head;
          while (true) {
              if (fast == null || fast.next == null) return null;
              fast = fast.next.next;
              slow = slow.next;
              if (fast == slow) break;
          }
          fast = head;
          while (slow != fast) {
              slow = slow.next;
              fast = fast.next;
          }
          return fast;
      
      }
  }
  

147. 对链表进行插入排序

示例 1：
输入: 4->2->1->3
输出: 1->2->3->4

示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5

逐个遍历，

判断是否需要排序（下个元素比现在的小）

调整位置（遍历已经排序的节点，找到适合插入的位置）。

class Solution {
    public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) {
            return head;
        }
        
        // 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
        // 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
        // 每次迭代完成，从插入元素为止，该链表可以被认为已经部分排序
        // 重复直到所有输入数据插入完为止
        
         // 1.遍历并与前面已经有序的序列向前逐一比较排序，找到合适为止插入
        
        // 定义三个指针 pre, cur, lat
        //pre 从前往后找到要插入的位置
        //cur 当前指向的指针
        //lat 记录下一个要插入排序的值
        // h  ->  4  ->  2  ->  5  ->  3  ->  null
        
        // 创建 h 节点，用于遍历链表
        ListNode h = new ListNode(-1);
        h.next = head;
        ListNode pre = h;
        ListNode cur = head;
        ListNode lat;
        
        while (cur != null) {
            lat = cur.next; // 记录下一个要插入排序的值
            
            if (lat != null && lat.val < cur.val) { // 只有 cur.next 比 cur 小才需要向前寻找插入点
                // 寻找插入点，从 pre 开始遍历 （每次都是头节点 h 开始向后遍历，因为单向链表是无法从后往前遍）
                while (pre.next != null && pre.next.val < lat.val) { 
                    pre = pre.next; // 从前往后找到要插入的位置
                }
                // 找到要插入的位置，此时 pre 节点后面的位置就是 lat 要插入的位置
                // 交换 pre 跟 lat 节点需要一个 temp 节点来临时保存下插入位置 node 后 next
                ListNode tmp = pre.next;
                pre.next = lat;
                cur.next = lat.next;
                lat.next = tmp;
                // 由于每次都是从前往后找插入位置，但是单向链表是无法从后往前遍历，所以需要每次插入完成后要让 pre 复位
                pre = h;
            } else {
                // 都这直接把 cur 指针指向到下一个
                cur = lat;
            }
        }
       return h.next;
    }
}

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

class Solution {
    public boolean isPalindrome(ListNode head) {
     if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;//翻转前半部分的链表
            prepre = pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
        while(pre != null && slow != null) {//开始比较
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;

    }
}

st = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;//翻转前半部分的链表
            prepre = pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
        while(pre != null && slow != null) {//开始比较
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;

    }
}