[数据结构与算法]剑指offer第二版 leetcode java

leetcode

LinkedList

剑指 Offer 06. 从尾到头打印链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
import java.util.ArrayList;
import java.util.Stack;
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode h = head;
        Stack<Integer> s = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        while (h != null) {
            s.push(h.val);
            h = h.next;
        }
        int[] a = new int[s.size()];
        int i = 0;
        while (s.size() > 0) {
            a[i++] = s.pop();
        }
        return a;

    }
}

剑指 Offer 22. 链表中倒数第k个结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode h = head;
        ListNode h2 = head;
        int size = 0;
        while (h != null) {
            size++;
            h = h.next;
        }
        for (int i = 0; i < size - k; i++) {
            h2 = h2.next;
        }
        return h2;
    }
}

剑指 Offer 24. 反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

剑指 Offer 25. 合并两个排序的链表

剑指 Offer 35. 复杂链表的复制

剑指 Offer 52. 两个链表的第一个公共节点

剑指 Offer 18. 删除链表的节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return null;
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            if (head.val == val) {
                head = cur.next;
                cur.next = null;
                return head;
            } else if (cur.val != val) {
                pre = cur;
                cur = cur.next;
            } else {
                pre.next = cur.next;
                cur.next = null;
                break;
            }
        }
        return head;

    }
}