链表 - 简书

1.链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点
分析：已知listnode 类，在解决solution类中写方法，获得倒数的第k个节点
方法：

遍历链表，得到链表长度为n，让指针向前进n-k步，可以得到结果
双指针，两个指针共同指向头节点，former前进k步以后，former latter共同往前走，直到former走到null停下来，latter指向的就是结果

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

2.反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
分析：第一反应是用栈，先进后出
方法：

外部容器，用java自己的API
双指针迭代：pre cur1.初始化：pre指向null，cur指向head 2.tmp记录好cur.next，然后让cur指向pre 3.cur pre前进一步 4.重复过程
递归

/**
 * 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;
        ListNode tmp = null;
        while(cur!=null)
        {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

3.两个链表第一个公共节点

分析:两个链表，同时开始遍历，若有一个链表遍历完毕则指向另一个链表的头节点，在下一次循环再同步遍历，直至两指针相遇。【简单来说，我走完自己的路，走你的路，两条路穿插走，直至相遇】相遇时，两节点走过的路程相同。

方法：1.对两个链表判空，空直接返回null 2.指针n1 指向链表一的head1，n2指向链表二的head2，往后遍历3.判空，如果走到头指向另一条链表的head，继续遍历4.直到两值相等
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

/**
 * 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 n1 = headA;
        ListNode n2 = headB;
        if(n1 == null ||n2 ==null)
        {
            return null;
        }
        while(n1!=n2)
        {
            n1 = n1 == null? headB : n1.next; 
            n2 = n2 == null? headA : n2.next;
        }
        return n1;

    }
}

4.删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

/**
 * 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;
        if(head.val == val) return head.next;
        ListNode cur = head;
        while(cur.next.val != val)
        {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return head;
    }
}

5.复杂链表的复制

复制的意思是指深拷贝（Deep Copy), 浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。

方法一：深度优先搜索
1从头结点 head 开始拷贝；
2由于一个结点可能被多个指针指到，因此如果该结点已被拷贝，则不需要重复拷贝；
3如果还没拷贝该结点，则创建一个新的结点进行拷贝，并将拷贝过的结点保存在哈希表中；
4使用递归拷贝所有的 next 结点，再递归拷贝所有的 random 结点

/*
// 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 {
    HashMap<Node,Node> map = new HashMap();
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node ptr = head;
        while(ptr!= null)
        {
            Node node = getnode(ptr);
            node.next = getnode(ptr.next);
            node.random = getnode(ptr.random);
            ptr = ptr.next;
        }
        return getnode(head);
        
    }

    private Node getnode(Node n)
    {
        if(n == null) return null;
        if(!map.containsKey(n))
        {
            Node tmp = new Node(n.val);
            map.put(n,tmp);
        }
        return map.get(n);
    }
}

方法二：拓展链表迭代，复制到每个节点旁边，然后再分离

/*
// 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;
        copy(head);
        randomdirect(head);
        return relist(head);
    }
    private void copy(Node head){
        while(head !=null)
        {
            Node copynode = new Node(head.val);
            Node nextnode = head.next;
            head.next = copynode;
            copynode.next = nextnode;
            head = copynode.next;
        }
    }

    private void randomdirect(Node head)
    {
        while(head!=null)
        {
            Node copynode = head.next;
            if(head.random!=null)
            {
                Node direct = head.random;
                copynode.random = direct.next;
            }
            head = copynode.next;
        }

    }
    private Node relist(Node head){
        Node cloneNode = head.next;
        Node cloneHead = cloneNode;
        head.next = cloneNode.next;
        head = head.next;
        while(head!=null){
            cloneNode.next = head.next;
            head.next = head.next.next;
            head = head.next;
            cloneNode = cloneNode.next;
        }
        return cloneHead;
    }

}

链表

1.链表中倒数第k个节点

2.反转链表

3.两个链表第一个公共节点

4.删除链表的节点

5.复杂链表的复制

推荐阅读更多精彩内容