【Leetcode】链表

题目编号

206 141 21 19 876 160

编写链表

public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

易犯错误

• 最近遇到一个问题：

---

head –> val = 6 –> val = 13 –> val = 17 –> val = 21

---

求head.next.next.val = ?

• 解题思路：
  因为头指针head只指向头节点所在的地址，并不包含数据，所以不能把头指针看作一个节点，所以head.next.next.val = 17.

206. 反转链表

解题思路

类似于选择排序中交换两个数的位置。借助一个tmp完成交换

代码

public ListNode reverseList(ListNode head) {
        ListNode pre = null; // 前元素
        ListNode cur = head; // 正在操作的元素
        ListNode tmp = null; // 临时元素
        while (cur != null) {
            tmp = cur.next; 
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

141. 环形链表

解题思路

因为如果是环形链表，一定会陷入无限循环。所以用快慢指针解决。

代码

public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode low = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            if(fast.equals(low)){
                // 慢指针追上了快指针
                return true;
            }
            low = low.next;
            fast = fast.next.next;
        }
        return false;
    }

21. 合并两个有序链表

解题思路

创建一个新链表，比较l1、l2两个链表的大小，将小的放进新链表。最后将剩余的接在新链表后面。

代码

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                curr = curr.next;
                l1 = l1.next;
            } else if (l1.val >= l2.val) {
                curr.next = l2;
                curr = curr.next;
                l2 = l2.next;
            }
        }
        if (l1 != null) {
            // 如果l1有剩余，将剩余元素接上去
            curr.next = l1;
        } else if (l2 != null) {
            // 与l1同理
            curr.next = l2;
        }
        // 装逼写法
        // cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }

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

解题思路

用快慢指针，中间相隔n个数，快指针到末尾时，慢指针指向的下一个元素就是要删除的节点。

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode low = dummy;
        ListNode fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            low = low.next;
        }
        if (low.next.next == null) {
            low.next = null;
        } else {
            low.next = low.next.next;
        }
        return dummy.next;

    }

876. 链表的中间节点

解题思路

先遍历链表数出有多少个元素，第（k/2+1）个元素就是中间元素。

代码

public ListNode middleNode(ListNode head) {
       ListNode dummy = new ListNode(0);
       dummy.next = head;
       ListNode low = dummy;
       ListNode fast = dummy;
       int k = 0;
       while (fast.next != null) {
           fast = fast.next;
           k++;
       }
       for (int i = 0; i < k / 2 + 1; i++) {
           low = low.next;
       }
       return low.next;
   }

160.相交链表

解题思路

首先初始化pA，pB开始遍历。当pA到尾巴的时候，回到pB开始遍历。pB同理。
这样pA的路线a+c+b，pB的路线b+c+a，可知他们如果有交点，一定在遍历的尾巴处。

如果两个链表没有相交，那么就变成了pA为a+b，pB为b+a，最终他们一定会遍历到null，所以返回其中一个即可。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;

        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}