剑指offer--链表相关

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

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head == null) return new int[]{};
        ListNode cur = head;
        int size = 0;
        while(cur != null){
            size++;
            cur = cur.next;
        }
        cur = head;
        int[] res = new int[size];
        for(int i = size - 1; i >= 0; i--){
            res[i] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<>();
        ListNode cur = head;
        while(cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }
        int[] res = new int[stack.size()];
        int index = 0;
        while(!stack.isEmpty()){
            res[index++] = stack.pop();
        }
        return res;
    }
}

剑指 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) {
        ListNode domp = new ListNode(-1);
        domp.next = head;
        ListNode tem = domp;
        while(tem.next != null){
            if(tem.next.val == val){
                tem.next = tem.next.next;
                break;
            }
            tem = tem.next;
        }
        return domp.next;
    }
}

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

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.

/**
 * 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 fir = head;
        ListNode sec = head;
        for(int i = 0; i < k; i++){
            fir = fir.next;
        }
        while(fir != null){
            fir = fir.next;
            sec = sec.next;
        }
        return sec;
    }
}

剑指 Offer 24. 反转链表

双指针法

剑指offer--链表相关 - 图10

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public 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;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head){
        //if(head == null) return null;
        return reverse(null,head);
    }
    public ListNode reverse(ListNode pre,ListNode cur) {
        if(cur == null) return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(cur,temp);
    }
}

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pom = new ListNode(0);
        ListNode cur = pom;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next  =l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return pom.next;
    }
}

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

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        //1.复制节点
        Node cur = head;
        while(cur != null){
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = cur.next.next;
        }
        //2.复制random节点
        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //3.分开链表
        Node dummy = new Node(-1);
        Node help = dummy;
        cur = head;
        while(cur != null){
            help.next = cur.next;
            help = help.next;
            cur.next = cur.next.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}

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

输入两个链表，找出它们的第一个公共节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode idxA = headA;
        ListNode idxB = headB;
        while(idxA != idxB){
            if(idxA == null){
                idxA  =headB;
            }else{
                idxA = idxA.next;
            }
            if(idxB == null){
                idxB = headA;
            }else{
                idxB = idxB.next;
            }
        }
        return idxA;
    }
}

707. 设计链表

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
};
class MyLinkedList {
    int length;
    ListNode head;
    /** 初始化构造器*/
    public MyLinkedList() {
        this.head=new ListNode(0);
        this.length=0;
    }
    /**获取索引值对应的节点值 */
    public int get(int index) {
        if(index<0||index>=length) return -1;
        ListNode p = head;
        for(int i=0;i<=index;i++) {//index=0,对应第1个节点，第一个节点即为head.next
            p=p.next;
        }
        return p.val;
    }
    /**在链表头添加节点 */
    public void addAtHead(int val) {
        ListNode first=new ListNode(val);
        first.next=head.next;
        head.next=first;
        length++;
        //addAtIndex(0,val);
    }
    /** 在链表尾部添加节点 */
    public void addAtTail(int val) {
        ListNode p=head;
        while(p.next!=null){
            p=p.next;
        } 
        p.next=new ListNode(val);
        length++;
    }
    /**在索引值为index的节点之前插入节点 */
    public void addAtIndex(int index, int val) {
        if(index < 0) index = 0;//addAtHead(val); return;
        if(index > length) return;
        /*if(index==length) { addAtTail(val); return; }*/
        length++;
        ListNode pre = head;
        for(int i = 0;i < index; i++){
            pre = pre.next;
        }
        ListNode temp=new ListNode(val);
        temp.next=pre.next;
        pre.next=temp;
    } 
    /** 如果索引 index 有效，则删除链表索引值为 index的节点。 */
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= length) return;
        length--;
        ListNode pre=head;
        for(int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;    
    }
}

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        //获取当前节点的下一个节点
        ListNode next = head.next;
        //进行递归
        ListNode newNode = swapPairs(next.next);
        //进行交换
        next.next = head;
        head.next = newNode;
        return next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode prev = dummyNode;
        while(prev.next != null && prev.next.next != null){
            ListNode temp = head.next.next;     //缓存next
            prev.next = head.next;              //将prev 的 next 改为 head 的next
            head.next.next = head;              //将head.next(prev.next) 的next 指向 head
            head.next = temp;                   //将 head 的 next 接上缓存的temp
            prev = head;                        //步进1位
            head = head.next;                   //步进1位
        }
        return dummyNode.next;
    }
}

141. 环形链表

给定一个链表，判断链表中是否有环

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) return true;
        }
        return false;
    }
}

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            //块慢指针相遇 从head和相遇点，同时查找直到相遇
            if(slow == fast){
                ListNode index1 = fast;
                ListNode index2 = head;
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index2;//返回环的入口
            }
        }
        return null;
    }
}

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next : head;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while(current != null && current.next != null){
            if(current.val == current.next.val){
                current.next = current.next.next;
            }else{
                current = current.next;
            }
         }
         return head; 
    }
}

234. 回文链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode current = head;
        while(current != null){
            list.add(current.val);
            current = current.next;
        }
        int first = 0;
        int last = list.size()-1;
        while(first < last){
            if(!list.get(first).equals(list.get(last))){
                return false;
            }
            first++;
            last--;
        }
        return true;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);
        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        
        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

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

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

划分链表