LeetCode题解_链表

链表

leetcode_160_easy

<leetcode_link>

• 问题描述
  给你两个单链表的头节点 headA和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

  输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
  输出：Intersected at '8'
  

• 解法：双指针

  A、B链表同时往后遍历，当遍历到末尾时分别从对方的head继续遍历，直到出现相同的节点或者均为null

• 原理

  假设AB存在交点，则有a+c+b=b+c+a，其中c为公共链长度，即AB存在某时刻二者遍历的长度相等，此时为交点。若不存在交点，则有a+b=b+a，即最后同时为null。

• 代码

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      ListNode l1 = headA, l2 = headB;
      while (l1 != l2) {
          l1 = (l1 == null) ? headB : l1.next;
          l2 = (l2 == null) ? headA : l2.next;
      }
      return l1;
  }
  

leetcode_206_easy

<leetcode_link>

• 问题描述
  反转链表

• 解法：头插法

  有时秒解有时想很久

• 原理

  创建一个新头节点和临时节点，头节点存放反转后的链表头，临时节点用于反转时存放当前反转链表的链表头。

• 代码

  public ListNode reverseList(ListNode head) {
  	ListNode newHead=null,tmpNode=null;
  	while(head!=null) {
  		tmpNode = newHead;
  		newHead = head;
  		head = head.next;
  		newHead.next = tmpNode;
  	}
  	return newHead;
  }
  

leetcode_21_easy

<leetcode_link>

• 问题描述
  按升序合并两个链表

• 解法：迭代

  递归想不明白就不用了

• 原理

  留一个头节点用于返回，注意两个链表不同长时合并剩余的单链

• 代码

  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
      if(list1==null){
          return list2;
      }
      if(list2==null){
          return list1;
      }
      ListNode head = new ListNode(),list = head;
      while(list1!=null&&list2!=null){
          if(list2.val>list1.val){
                 list.next = list1;
                 list1=list1.next; 
          }
          else{
                 list.next = list2;
                 list2=list2.next; 
  
          }
          list=list.next;
      }
      list.next = list1==null?list2:list1;
  
      return head.next;
  }
  

References

• https://leetcode.cn/
• http://www.cyc2018.xyz/