常用技巧与操作

技巧

1. 多画图！！直观且形象，便于理解指向关系。
2. 引入虚拟头结点，可以使代码统一，便于处理边界情况，也方便对链表操作
3. 大胆创建局部变量。
   举个例子：在双向链表中插入新节点，需要写四行代码，并且顺序不能随便改，要保证链表不断开，思路很复杂。而引入了局部变量就价低了思考成本，避免链表断开的问题。
   
   4. 快慢双指针 是非常经典的解法，可以解决判断是否有环、找环入口、俩链表中倒数第N个节点等问题

操作

1. 创建新节点：new ListNode()
2. 尾插： 创建尾指针tail维护链表最后一个节点，tail.next = node tail = node
3. 头插： newhead.next = head.next head = newhead方便进行逆序链表操作

1. 两数相加（LC2）

两数相加

题目描述

解题思路

直接模拟两数相加过程

1. 创建虚拟头结点head
2. cur1和cur2分别遍历两个链表，t保存cur1与cur2指向数的和，结果链表中尾插t的末位
3. 如果上一次产生了进位，剔除t的末位，此时剩余的1表示进位，t继续 += cur1 与cur2指向的数.

代码解析

class Solution {
    ListNode head = new ListNode();
    ListNode tail = head;

    //尾插
    private void addLast(int val){
        ListNode node = new ListNode(val);
        tail.next = node;
        tail = node;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        int t = 0;
        while(cur1 != null && cur2 != null){
            t += cur1.val + cur2.val;
            addLast(t%10);
            t /= 10;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        while(cur1 != null){
            t += cur1.val;
            addLast(t%10);
            t/=10;
            cur1 = cur1.next;
        }

        while(cur2 != null){
            t += cur2.val;
            addLast(t%10);
            t/=10;
            cur2 = cur2.next;
        }
        if(t==1)
            addLast(1);

        return head.next;
    }
}

注意： 如果最后t还为1，说明还有进位，要在结尾加上新节点，值为1.

拓展：链表相加二（NC40）

链表相加二

相加前需要把两个链表进行逆序操作，得到的结果也要逆序后返回。

public class Solution { 
    //逆序
    private ListNode reverse(ListNode node){
        ListNode head = new ListNode(0);
        ListNode cur = node;
        while(cur!=null){
            ListNode newNode = new ListNode(cur.val);
            newNode.next = head.next;
            head.next = newNode;
            cur = cur.next;
        }
        return head.next;
    }
    
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode cur1  = reverse(head1);
        ListNode cur2  = reverse(head2);

        ListNode head = new ListNode(0);
        ListNode tail = head;
        int t = 0;
        while(cur1 != null || cur2 != null || t!=0){
            if(cur1 != null){
                t += cur1.val;
                cur1 = cur1.next;
            }
            if(cur2 != null){
                t += cur2.val;
                cur2 = cur2.next;
            }
            tail.next = new ListNode(t%10);
            tail = tail.next;
            t /= 10;
        }
        head = reverse(head.next);
        return head;
    }
}

2. 两两交换链表中的节点（LC24）

两两交换链表中的节点

题目描述

解题思路

1. 如果链表为空或者只有一个节点直接返回原节点
2. 定义头结点，方便处理边界情况
3. 定义四个变量prev,cur,curNext,curNNext，交换cur和curNext.
4. prev更新到cur位置，cur更新到prev下一个。
   
   
5. 通过画图发现偶数个节点最后cur为null，奇数个节点最后curNext为null，因此curNext和curNNext更新时要先判断这两个引用是不是为null。

代码解析

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

        //cur curNext不为空
        ListNode newHead = new ListNode();
        ListNode prev =  newHead;
        prev.next = head;
        ListNode cur = head;
        ListNode curNext = cur.next;
        ListNode curNNext = curNext.next;

        while(cur!=null && curNext!=null){
            //交换节点
            prev.next = curNext;
            curNext.next = cur;
            cur.next = curNNext;
            
            //修改指针
            prev = cur;
            cur = prev.next;
            if(cur != null)
                curNext = cur.next;
            if(curNext != null) 
                curNNext = curNext.next;
        }
        return newHead.next;
    }

3. 重排链表（LC143）

重排链表

题目描述

解题思路

1. 找到链表的中间节点：快慢双指针
2. 把右半部分逆序：头插法
3. 合并两个链表
   

代码解析

public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next==null)
            return;

        //1.找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //此时slow是中间节点 

        //2.翻转右半部分
        ListNode newHead = new ListNode();
        ListNode cur = slow.next;
        //把两个链表分离，避免后面出环
        slow.next = null;
        while(cur!=null){
            //头插法
            ListNode curNext = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = curNext;
        }

        //3.合并两个链表
        ListNode cur1 = head;
        ListNode cur2 = newHead.next;
        while(cur1!=null && cur2!=null){
            ListNode cur1Next = cur1.next;
            ListNode cur2Next = cur2.next;
            cur1.next = cur2;
            cur2.next = cur1Next;
            cur1 = cur1Next;
            cur2 = cur2Next;
        }
    }

4. 合并K个升序链表（LC23）

合并K个升序链表

题目描述

解题思路

• 解法一： 仿照合并两个有序链表的思路。
  1. 创建k个指针，分别指向链表头
  2. 创建小根堆，令k个节点全部入队，每次取堆顶元素，即最小值，合并到结果链表。
• 解法二： 分治思想
  类似归并排序，细分到两个有序链表进行排序，接着合并，直到合并为一个链表

代码解析

• 思路一：

public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        //1. 创建小根堆、把头结点依次放入小根堆中
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for (ListNode node : lists) {
            if (node != null)
                heap.offer(node);
        }

        //2. 合并链表
        ListNode head = new ListNode();
        ListNode tail = head;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            if(node.next!=null)
                heap.offer(node.next);
            //尾插
            tail.next = node;
            tail = tail.next;
            
        }
        return head.next;
    }

• 思路二

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }

    ListNode merge(ListNode[] lists,int left,int right){
        if(left>right)
            return null;
        if(left == right)
            return lists[left];
        //1. 平分数组，递归左右两部分
        int mid = left + (right - left)/2;
        ListNode l1 =  merge(lists,left,mid);
        ListNode l2 =  merge(lists,mid+1,right);

        //2. 合并两个链表
        return combine(l1,l2);
    }
    ListNode combine(ListNode l1,ListNode l2){
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        ListNode ret = new ListNode();
        ListNode tail = ret;
        ListNode cur1 = l1;
        ListNode cur2 = l2;

        while(cur1!=null && cur2!=null){
            if(cur1.val <= cur2.val){
                tail.next = cur1;
                cur1 = cur1.next;
            }else{
                tail.next = cur2;
                cur2 = cur2.next;
            }
            tail = tail.next;
        }
        if(cur1!=null)
            tail.next = cur1;
        if(cur2!=null)
            tail.next = cur2;
        return ret.next;
    }
}

5. K个一组反转链表

K个一组反转链表

题目描述

解题思路

1. 求出需要逆序多少组：n
2. 重复n次，长度为k的链表的链表逆序（头插法）

注意： 定义flag标记每组的首节点，定义tail维护链表的尾节点。头插后，flag恰好指向尾节点，把tail移动到flag位置，方便下一组链表衔接。

代码解析

public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null)
            return null;

        int len = 0;
        ListNode cur = head;
        while(cur!=null){
            len++;
            cur = cur.next;
        }
        int n = len/k;

        ListNode ret = new ListNode();
        ListNode tail = ret;
        cur = head;

        for(int i = 0;i < n;i++){
            ListNode flag = cur;

            //头插法 
            for(int j = 0;j < k;j++){
                ListNode curNext = cur.next;
                cur.next =tail.next;
                tail.next = cur;
                cur = curNext;
            }
            tail = flag;
        }
        //把最后的尾巴拼接
        tail.next = cur;
        return ret.next;
    }