2019-08-01

链表题【翻转链表】【环形链表】【删除重复元素】【两数相加】【相交链表】

链表的定义

static class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

1.翻转链表

https://leetcode-cn.com/problems/reverse-linked-list/
递归：

在遍历链表时，将当前节点cur的next指向前一个元素，
由于节点没有引用上一个节点，故初始时设置前一个节点pre = null,
在更改引用之前，还需要另一个指针来存储下一个节点next = cur.next。

// 执行用时 :1 ms, 在所有 Java 提交中击败了85.90%的用户
// 内存消耗 :36.1 MB, 在所有 Java 提交中击败了55.82%的用户
public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;  //将下一个节点记录
        cur.next = pre;  //当前节点指向上一个节点
        pre = cur;   //记录当前节点
        cur = next; //将下一个节点变成当前节点
    }
    return pre;
}

迭代：假设链表为 n1–>n2–>n3—n>4–>null,若某部分已经被翻转了 n1–>n2–>n3<--n4，我们希望3指向2，所以有n3.next.next = n2,要注意n1的下一个必须指向null,故还有个head.next = null操作。

public static ListNode reverseList(ListNode head) {
    if(head == null || head.next == null)
        return head;
    ListNode res = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return res;
}

2.翻转链表II

https://leetcode-cn.com/problems/reverse-linked-list-ii/
假设以 head – 1–2–3–4–中的1~4进行反转

先让头指针的next指向2，
再让1的next指向3，
最后将2的next指向1，

完成第一次交换，顺序变成header–2–1–3–4,

然后进行相同的交换将结点3移动到结点2的前面，然后再将结点4移动到结点3的前面就完成了反转。

同

>     class Solution {
>     public ListNode reverseBetween(ListNode head, int m, int n) {
>        ListNode res = new ListNode(0);
>        res.next = head;
>        ListNode pre = res;
>        for(int i = 1; i < m; i++){
>            pre = pre.next;
>        }
>        head = pre.next;
>        for(int i = m; i < n; i++){
>            ListNode nextnode = head.next;
>            head.next = nextnode.next;
>            nextnode.next = pre.next;
>            pre.next = nextnode;
>        }
>        return res.next;
>     }
>     }
>

3.环形链表

https://leetcode-cn.com/problems/linked-list-cycle/
方法1：HashSet,如果当前结点存在于哈希表中，说明有环，否则遍历完全，返回false。

public static boolean hasCycle(ListNode head) {
     Set<ListNode> res = new HashSet<>();
     while (head !=null){
         if(res.contains(head)){
             return true;
         }else{
             res.add(head);
         }
         head = head.next;
     }
     return false;
 }

方法2：快慢指针，快指针先于慢指针一步，如果有环，总有一个时刻快指针会追上慢指针。

//执行用时 :1 ms, 在所有 Java 提交中击败了92.84%的用户
//内存消耗 :39.6 MB, 在所有 Java 提交中击败了47.88%的用户
   public static boolean hasCycle(ListNode head) {
       if (head == null || head.next == null) 
             return false;
       ListNode fast = head.next;
       ListNode slow = head;
       while(fast !=slow){
           if(fast==null || fast.next==null){
               return false;
           }
           fast = fast.next.next;
           slow = slow.next;
       }
       return true;
    }

4.环形链表II

https://leetcode-cn.com/problems/linked-list-cycle-ii/

快慢指针：当fast和slow在环中相遇时，设头节点到入环结点的长度为x,入环结点到相遇点长度为y,相遇点到入环结点长度为z,则有(x+y)*2 = x+y+z+y,即x = z,把快指针设为头节点，慢指针还在相遇点，两个指针相遇之时就是入环点所在之处。

//执行用时 :1 ms, 在所有 Java 提交中击败了99.71%的用户
//内存消耗 :36.3 MB, 在所有 Java 提交中击败了5.03%的用户
public ListNode detectCycle(ListNode head) {
          if(head == null || head.next == null)
              return null;
          ListNode fast = head;
          ListNode slow = head;
          while(fast.next!=null && fast.next.next!=null){
              fast = fast.next.next;
              slow = slow.next;
              //环内相遇
              if(fast == slow){
                  //快指针重头走
                  fast = head;
                  //快慢指针同时走，相等时即入环结点处
                  while(fast !=slow){
                      fast = fast.next;
                      slow = slow.next;
                  }
                  return fast;
              }
          }
          //走到尾巴了，说明没有环
          return null;
      }

5.两数相加

https://leetcode-cn.com/problems/add-two-numbers/

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode ress = new ListNode(0);
    ListNode res = ress;
    int flag = 0;
    while(l1!=null ||l2!=null){
        int x = l1!=null ?l1.val:0;
        int y = l2!=null?l2.val:0;
        int value = x+y+flag;
        flag = value/10;
        res.next = new ListNode(value%10);
        res = res.next;
        if(l1!=null)
            l1 = l1.next;
        if(l2!=null)
            l2 = l2.next;
    }
    if(flag>0)
        res.next = new ListNode(flag);
    return ress.next;
  
}

6.两数相加II

https://leetcode-cn.com/problems/add-two-numbers-ii/submissions/

思路1：使用翻转，进行计算，结果再次翻转即可

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  if(l1 == null && l2!=null)
      return l2;
  if(l2 == null && l1!=null)
      return l1;
  ListNode head1 = reverseList(l1);
  ListNode head2 = reverseList(l2);
  ListNode res = new ListNode(-1);
  ListNode ans = res;
  int count = 0;
  while (head1!=null || head2 != null){
      int x = head1 == null ? 0 : head1.val;
      int y = head2 ==null ? 0:head2.val;
      res.next = new ListNode((x+y+count)%10);
      count = (x + y +count)/10;
      res = res.next;
      if(head1!=null) head1 = head1.next;
      if(head2!=null) head2 = head2.next;
  }
  if(count != 0){
      res.next = new ListNode(count);
  }
  ListNode root = reverseList(ans.next);
  return root;
}
private static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur!=null){
        ListNode nextnode = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nextnode;
     }
    return pre;
}

思路2：不使用翻转，使用栈进行存储


public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      Stack<Integer> stack1=new Stack();
      Stack<Integer> stack2=new Stack();
      ListNode node1=l1;
      //将l1的值入栈
      while(node1!=null){
          stack1.push(node1.val);
          node1=node1.next;
      }
      //将l2的值入栈
      ListNode node2=l2;
      while(node2!=null){
          stack2.push(node2.val);
          node2=node2.next;
      }
      ListNode head=null;
      int flag=0;
      //依次弹出
      while(!stack1.isEmpty()||!stack2.isEmpty()||flag!=0){
          int value=0;
          if(!stack1.isEmpty())
              value+=stack1.pop();
          if(!stack2.isEmpty())
              value+=stack2.pop();
          value+=flag;
          ListNode node=new ListNode(value%10);
          flag=value/10;
          //计算的低位依次向后移动
          node.next=head;
          //head存储上一次计算得到的值
          head=node;
      }
      return head;
  }

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

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

public ListNode deleteDuplicates(ListNode head) {
       if(head == null || head.next == null)
           return head;
       ListNode node = head;
       while(node!=null && node.next!=null){
              //如果相等则跳过这个数
           if(node.val == node.next.val){
               node.next = node.next.next;
           }else{
               node = node.next;
           }
       }
       return head;
   }

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

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

public static ListNode deleteDuplicates(ListNode head) {
    if(head==null || head.next==null)
        return head;
    //head的首部也是重复的数
    if(head.val==head.next.val){
        //node的首部为重复的数，此时head的首部也是重复的数
        ListNode node = head.next;
        //如果node的首部一直跟head的相同，则一直向后移动，直到不是重复的数
        while( node != null && head.val == node.val ){
            node = node.next;
        }
        //递归node结点，此时node结点为删除了前面重复的数
        return deleteDuplicates(node);
    }else{
        //不相等就向下移动，递归删除后面重复的数
        head.next = deleteDuplicates(head.next);
        return head;
    }
}

9.相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
关键：消除两个链表的长度差

指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历

比较长的链表指针指向较短链表head时，长度差就消除了

如此，只需要将最短链表遍历两次即可找到位置

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
    pA = pA == null ? headB : pA.next;
    pB = pB == null ? headA : pB.next;
}
return pA;
}

本文标题:链表题【翻转链表】【环形链表】【删除重复元素】【两数相加】【相交链表】

文章作者:qiulig

发布时间:2019-08-01, 15:19:11

最后更新:2019-08-01, 15:22:16

文章字数:1.9k

原始链接:http://blogs.qiulig.website/2019/08/链表题【翻转链表】【环形链表】【删除重复元素】【两数相加】【相交链表】/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。