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;
}
}
