1.1. 基本结构


1.2. 剑指Offer 面试题

1.2.1. 从尾到头打印链表

这一题需要考虑的是是否能改变原始数据的样式,我们默认不改变。因此,使用一种简单的方式,就是使用结构,先将链表的数据一个个压入栈,然后再弹出即可。

  • 时间:o(n),空间:o(n)
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> l1 = new ArrayList<>();
        Stack<Integer> st = new Stack<>();
        // 1. 压栈
        while (listNode != null) {
            st.push(listNode.val);
            listNode = listNode.next;
        }
        // 2. 出栈
        while (!st.empty()) {
            l1.add(st.pop());
        }
        return l1;
    }
}

1.2.2. 相交链表

编写一个程序,找到两个单链表相交的起始节点。

  • 方法一:遍历A链表,使用Set存储节点;然后遍历B,找到Set中包含B的节点的数据返回。

    时间:O(m+n),空间:O(m)或O(n)

    //method 1.使用hashMap
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<Integer> set = new HashSet<>();
        while(headA != null){
            set.add(headA.hashCode());
            headA = headA.next;
        }
        while(headB != null){
            if (set.contains(headB.hashCode())){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
  • 方法二:追赶法

    时间:O(m+n),空间:O(1)

    设 A 的长度为 a + c,B 的长度为 b + c,其中 c 为尾部公共部分长度,可知 a + c + b = b + c + a。

    当访问 A 链表的指针访问到链表尾部时,令它从链表 B 的头部开始访问链表 B;

    同样地,当访问 B 链表的指针访问到链表尾部时,令它从链表 A 的头部开始访问链表 A。

    这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

    如果不存在交点,那么 a + b = b + a,以下实现代码中 l1 和 l2 会同时为 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;
    }

1.2.3. 反转链表

设置一个Prev、Curr 和 temp变量,Prev和Curr用于反转数据,temp用于记录Curr的原始数据的下一个节点。

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null){
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }

递归:

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

1.2.4. 合并两个有序链表

题目的意思:就是将两个链表合并.

  • 使用递归的方法,每次查找l1和l2中较小的那个数,然后将当前node指向它,直到l1和l2均为空。

    时间:O(n+m),空间:O(1)

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
  • 常规法:
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        while (l1 != null && l2 != null){
            if(l1.val < l2.val){
                node.next = l1;
                l1  = l1.next;
                node = node.next;
            }else{
                node.next = l2;
                l2 = l2.next;
                node = node.next;
            }
        }
        node.next = l1!=null? l1:l2;
        return head.next;
    }

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

在一个排序好的链表中,删除相邻重复的数据。

遍历链表,通过记录前一个值prev和当前值curr,比较它们的值是否相同。

  • 如果相同,将prev指向curr.next,并更新curr。
  • 如果不同,则将prev和curr向后移一位。

时间O(n),空间O(1)

    public ListNode deleteDuplicates(ListNode head) {
        if(head == null||head.next == null) return head;
        ListNode prev = head;
        ListNode curr = head.next;
        while (curr != null){
            if (curr.val == prev.val) {
                curr = curr.next;
                prev.next = curr;
            }else {
                prev = curr;
                curr = curr.next;
            }
        }
        return head;
    }

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

思路就是:

  1. 记录当前node和 当前节点的倒数第n+1个节点
  2. 如果长度N与链表长度一致,将head去掉。如果长度N小于链表长度一致,则同时将node与prev移动到最后一位。
  3. 去除第N个节点

时间O(n),空间O(1)

    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return head;
        ListNode node = head;// 当前node
        ListNode prev = head;// 当前节点的倒数第n+1个节点
        // 1. 将node移动的相应位置
        for (int i = 0; i < n ; i++) {
            if (node == null){
                return null;
            }else{
                node = node.next;
            }
        }
        // 2.1 如果长度与链表长度一致,将head去掉。
        if (node == null) return head.next;
        // 2.2 如果长度小于链表长度一致,则同时将node与prev移动到最后一位
        while(node.next != null){
            node = node.next;
            prev = prev.next;
        }
        // 3. 将prev的next节点向后移动一位,去除第N个节点
        prev.next = prev.next.next;
        return head;
    }

1.3. LeetCode 面试题

1.3.1. 19. 删除链表的倒数第N个节点(中等)

使用双指针方法解决。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 为了避免空指针问题,在链表前面加上一个节点。(防止(1,1)的问题)
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    ListNode last = dummy;
    // 移动到末尾
    for (int i = 0; i < n; i++) {
        last = last.next;
    }
    while (last.next != null) {
        last = last.next;
        prev = prev.next;
    }
    prev.next = prev.next.next;
    return dummy.next;
}

1.3.2. 21. 合并两个有序链表(简单)

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 返回的指针头
    ListNode head = new ListNode(0);
    ListNode node = head;
    // 判断两个指针的val大小,将node指向过去。
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            node.next = l1;
            l1 = l1.next;
        } else {
            node.next = l2;
            l2 = l2.next;
        }
        node = node.next;
    }
    // 判断哪个链表还没有结束,将没结束的数据接上。
    if (l1 != null) {
        node.next = l1;
    } else if (l2 != null) {
        node.next = l2;
    }
    return head.next;
}

1.3.3. 24. 两两交换链表中的节点(中等)

使用三个指针,进行交换。

public ListNode swapPairs(ListNode head) {
    ListNode prev, curr;
    // 1. 添加一位,便于返回和交换数据
    ListNode node = new ListNode(0);
    node.next = head;
    // 2. 将head指向该首位
    head = node;
    // 3. 遍历数据,如果还有两两一起的数据,则继续交换
    while (node.next != null && node.next.next != null) {
        // 给指针赋值
        prev = node.next;
        curr = node.next.next;
        // 进行数字交换
        node.next = curr;
        prev.next = curr.next;
        curr.next = prev;
        node = prev;
    }
    return head.next;
}

1.3.4. 25. K 个一组翻转链表(困难)

没太看懂

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre = dummy;
    ListNode end = dummy;

    while (end.next != null) {
        for (int i = 0; i < k && end != null; i++) {
            end = end.next;
        }
        if (end == null) {
            break;
        }
        ListNode start = pre.next;
        ListNode next = end.next;
        end.next = null;
        pre.next = reverse(start);
        start.next = next;
        pre = start;

        end = pre;
    }
    return dummy.next;
}

private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

1.3.5. 83. 删除排序链表中的重复元素(简单)

记录前一个数据,然后进行遍历。O(n)

public ListNode deleteDuplicates(ListNode head) {
    //初始化初始节点
    ListNode node = head;
    // 遍历所有节点
    while (node != null) {
        ListNode next = node.next;
        // 如果存在相同节点,则改变指针指向,并node停留在此,方式连续多个重复数字出现
        if (next != null && next.val == node.val) {
            node.next = next.next;
        } else {
            // 不存在,则直接更新node
            node = node.next;
        }
    }
    return head;
}

1.3.6. 141. 环形链表(简单)

  1. 使用长短指针
public boolean hasCycle(ListNode head) {
    // 开始就是空,直接返回false
    if (head==null || head.next==null){
        return false;
    }
    // 使用快慢指针
    ListNode slow = head;// 慢指针
    ListNode fast = head;// 快指针
    while (fast != null && fast.next != null) {// 因为fast存在slow肯定也存在
        // 更新快慢指针
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}
  1. 使用hashMap

1.3.7. 142. 环形链表 II(中等)

  1. 使用长短指针

    首先,通过长短指针判断是否有环,如果有的执行下一步,没有的话,返回null 其次,假设 到入口的距离是H,环的长度是C,第一次相遇的位置是D。

    所以,慢指针 slow = H+mC+D,m为自然数,快指针fast = H+nC+D,n为自然数

    因为快指针是慢指针的两倍,所以2*dis_slow = dis_fast => H = (n-2m)C - D => H = kC - D。可以将k看成1。

    最后,让慢指针回到head节点,和fast同时以步长为1的速度跑。

    此时,等他们两相遇时候,慢节点运动H,快节点运动C-D的长度。此时返回H节点位置即可。

public ListNode detectCycle(ListNode head) {
    // 开始就是空,直接返回false
    if (head==null || head.next==null){
        return null;
    }
    // 使用快慢指针
    ListNode slow = head;// 慢指针
    ListNode fast = head;// 快指针
    while (fast != null && fast.next != null) {// 因为fast存在slow肯定也存在
        // 更新快慢指针
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow) {
            slow = head; // 将慢指针放到初始位置
            while (slow != fast) {//让他们同一速度跑
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}
  1. 使用hashMap

1.3.8. 160. 相交链表(简单)

  1. 暴力两层循环

  2. 使用hashMap

  3. 使用双指针

    初始化指针,让他们分别遍历链表A和链表B,如果它们有交点,则会相交,否则都会指向null。

    假设从A起点到相交点的距离为a,从B起点到相交点的距离为b,从相交点到末尾的距离为c。

    那么a+c+b=b+c+a

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

1.3.9. 206.反转链表(简单)

  1. 迭代法
public ListNode reverseList(ListNode head) {
    ListNode prev = null;// 记录prev
    ListNode curr = head;// 记录
    while (curr != null) {
        ListNode next = curr.next;//找到下一个节点
        curr.next = prev; // 将现在的节点指向前一个节点
        // 更新到下一个节点
        prev = curr; 
        curr = next;
    }
    return prev;
}

1.3.10. 234. 回文链表(简单)

  1. 找到中心点,反转链表,直接比较

    首先,明确,如果是对称的,那么链表长度一定是偶数。那么使用快慢指针,则可找到他的中心位置。

    然后,从中心点开始反转链表。

    最后,将反转后的链表与之前的链表进行比较。

public boolean isPalindrome(ListNode head) {
    if (head==null){
        return false;
    }
    ListNode slow = head;
    ListNode fast = head;
    // 找到中心点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 从中心点反转链表
    ListNode prev = null;
    ListNode curr = slow;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    //比较
    while (head.val == prev.val) {
        head = head.next;
        prev = prev.next;
        if (prev==null){
            return true;
        }
    }
    return false;
}

ps:此题有误,占用空间指的是操作写入的空间。所以不可能为O(1)。摘抄上原文

It is a common misunderstanding that the space complexity of a program is just how much the size of additional memory space being used besides input. An important prerequisite is neglected the above definition: the input has to be read-only. By definition, changing the input and change it back is not allowed (or the input size should be counted when doing so). Another way of determining the space complexity of a program is to simply look at how much space it has written to. Reversing a singly linked list requires writing to O(n) memory space, thus the space complexities for all "reverse-the-list"-based approaches are O(n), not O(1).

Solving this problem in O(1) space is theoretically impossible due to two simple facts: (1) a program using O(1) space is computationally equivalent to a finite automata, or a regular expression checker; (2) the pumping lemma states that the set of palindrome strings does not form a regular set.

Please change the incorrect problem statement.

1.3.11. 328. 奇偶链表(中等)

使用两个指针分别记录奇数和偶数,如果到结尾了,就将奇数的尾巴接上偶数的头。

public ListNode oddEvenList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) {
        return head;
    }
    ListNode odds = head; // 奇数
    ListNode even = head.next; // 偶数
    ListNode evenHead = even; // 偶数头
    while (even != null && even.next != null) {
        odds.next = even.next; // 奇数 => 偶数.next
        odds = odds.next;// 奇数 = 偶数.next
        even.next = odds.next;// 偶数 => 奇数.next
        even = even.next;// 偶数 = 奇数.next
    }
    odds.next = evenHead;
    return head;
}

1.3.12. 445. 两数相加 II(中等)

借助栈,进行计算。首先将两组数据全部压入栈中,然后利用栈先进后出的特点,从末尾开始计算。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // 1. 压栈
    Stack<ListNode> s1 = new Stack<>();
    Stack<ListNode> s2 = new Stack<>();
    while (l1 != null) {
        s1.push(l1);
        l1 = l1.next;
    }
    while (l2 != null) {
        s2.push(l2);
        l2 = l2.next;
    }

    // 2.出栈计算
    int flag = 0;//标志位,用于计进位数
    ListNode head = new ListNode(0);//用于做链表的头
    while (!s1.isEmpty() || !s2.isEmpty()) {
        int n1 = s1.isEmpty() ? 0 : s1.pop().val;
        int n2 = s2.isEmpty() ? 0 : s2.pop().val;
        int sum = n1 + n2 + flag;
        flag = sum / 10;
        ListNode node = new ListNode(sum % 10);
        // 将节点每次都加在头节点的后面即可
        node.next = head.next;
        head.next = node;
    }
    head.val = flag;
    if (head.val == 0) {
        return head.next;
    } else {
        return head;
    }
}

1.3.13. 725. 分隔链表(中等)

没太看懂。。。抄的官方的代码。

public ListNode[] splitListToParts(ListNode root, int k) {
    // 遍历数据得到长度
    ListNode cur = root;
    int n = 0;
    while (cur != null) {
        n++;
        cur = cur.next;
    }
    // 定义长度
    int width = n / k, rem = n % k;
    ListNode[] ans = new ListNode[k];
    cur = root;
    for (int i = 0; i < k; ++i) {
        ListNode head = new ListNode(0), write = head;
        for (int j = 0; j < width + (i < rem ? 1 : 0); ++j) {
            write = write.next = new ListNode(cur.val);
            cur = cur.next;
        }
        ans[i] = head.next;
    }
    return ans;
}

results matching ""

    No results matching ""