算法训练营——链表的相关问题

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

package 计算机程序算法分类.链表问题;

/**
 * @Classname 链表的两两节点交换
 * @Description TODO
 * @Date 2021/8/6 22:45
 * @Created by xjl
 */
public class 链表的两两节点交换 {
    class ListNode {
        int val;
        ListNode next;

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

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }

    public ListNode swapPairs2(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        // 只有当prev指向的结点之后有两个结点时才需要交换
        while (prev.next != null && prev.next.next != null) {
            ListNode node1 = prev.next;
            ListNode node2 = node1.next;
            ListNode subHead = node2.next;

            node2.next = node1;
            node1.next = subHead;
            prev.next = node2;

            // prev指向交换后的结点的第二个结点，
            // 即未交换结点的前一个结点
            prev = node1;
        }
        return dummyHead.next;
    }

    public ListNode swapList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode dumy = new ListNode(-1);
        dumy.next = head;

        ListNode pre = dumy;
        while (pre.next != null && pre.next.next != null) {
            ListNode node1 = pre.next;
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;
            //链表的调换
            node2.next = node1;
            node1.next = node3;
            pre.next = node2;

            //将下一个开始
            pre = node1;
        }
        return dumy.next;
    }

}

判断链表是否有环，同时的找到的链表的入口位置

package 计算机程序算法分类.链表问题;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * @Classname 链表成为环
 * @Description TODO
 * @Date 2021/8/6 22:10
 * @Created by xjl
 */
public class 链表成为环 {
    class ListNode {
        int val;
        ListNode next;

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

    /**
     * @description TODO 单纯的使用遍历来实现
     * @param: head
     * @date: 2021/8/6 22:31
     * @return: boolean
     * @author: xjl
     */
    public boolean hascycle(ListNode head) {
        if (head == null) {
            return false;
        }
        Set set = new HashSet();
        while (head != null) {
            //如果有环的那就true
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(2);
        ListNode s3 = new ListNode(1);
        ListNode s4 = new ListNode(2);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s2;

        boolean result = hascycle(s1);
        System.out.println(result);

    }

    /**
     * @description TODO 这个就是的使用了快慢指针的方法来实现这个原理
     * @param: head
     * @date: 2021/8/6 22:31
     * @return: boolean
     * @author: xjl
     */
    public boolean hascycle2(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    public ListNode hascycle2index(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                //表示入口和出口已经想遇了，这个时候你的将fast=head同时 设置步数为
                fast = head;
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

指 Offer 35. 复杂链表的复制

package 剑指offer练习题目;

import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname 复制一个复杂链表
 * @Description TODO
 * @Date 2021/8/7 10:06
 * @Created by xjl
 */
public class 复制一个复杂链表 {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        Node cur = head;
        Map map = new HashMap();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}