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

leetcode

链表的定义

1
2
3
4
5
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
2
3
4
5
6
7
8
9
10
11
12
13
// 执行用时 :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操作。

1
2
3
4
5
6
7
8
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的前面就完成了反转。

    • 同

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      >     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。

1
2
3
4
5
6
7
8
9
10
11
12
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//执行用时 :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
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    //执行用时 :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/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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：使用翻转，进行计算，结果再次翻转即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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： 不使用翻转，使用栈进行存储 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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时，长度差就消除了

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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" 转载请保留原文链接及作者。

文章目录
  1. 1. 链表的定义
  2. 2. 1.翻转链表
  3. 3. 2.翻转链表II
  4. 4. 3.环形链表
  5. 5. 4.环形链表II
  6. 6. 5.两数相加
  7. 7. 6.两数相加II
  8. 8. 7.删除排序链表中的重复元素
  9. 9. 8.删除排序链表中的重复元素II
  10. 10. 9.相交链表
| 139.6k