chapter02-链表

tip：设置虚拟头结点

public ListNode deleteNode (ListNode head, int val) { 
                 删除//链表，引入虚拟头结点很重要         ListNode dummy = new ListNode(-1);         dummy.next = head;         ListNode pre = dummy;         while(head != null){ 
                     if(head.val == val){ 
                         ///添加一条线，cur前一个结点->cur后一个结点                 pre.next=head.next;                 return dummy.next;             }             pre=head;             head = head.next;         }         return dummy.next; } 

tip:简单考察代码能力。

class ListNode { 
             int val;     ListNode next;     ListNode(){ 
        }     ListNode(int val) { 
                 this.val=val;     } } class MyLinkedList { 
             //size存储链表元素的数量     int size;     //虚拟头结点     ListNode head;      public MyLinkedList() { 
        
        size=0;
        head = new ListNode(0);
    }
    
    //方法
    ...
}

1.改变结点的指向方向，双指针，空间复杂度O(1)

public ListNode reverseList(ListNode head) { 
        
		if(head == null) return head;
		        ListNode cur = head;
		        ListNode pre = null;
		        ListNode tmp = null;
		        while(cur!=null){ 
        
		            tmp = cur.next;//保存下一个需要遍历的结点
		            cur.next=pre;
		            pre=cur;
		            cur=tmp;
		        }
        return pre;//返回新的头结点
}

2.递归

//递归终止条件是当前为空，或者下一个节点为空
public ListNode reverseList(ListNode head) { 
        
		if(head==null || head.next==null) { 
        
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);
		//这里请配合动画演示理解
		//如果链表是 1->2->3->4->5，那么此时的cur就是5
		//而head是4，head的下一个是5，下下一个是空
		//所以head.next.next 就是5->4

        //方向调转，增加一条新线，删除一条旧线
        //当前结点的后一个结点，指向当前结点
		head.next.next = head;
		//原来的指向删除
		head.next = null;
		//每层递归函数都返回cur，也就是最后一个节点
		return cur;
}

找到反转区间，遍历区间，插入到尾部结点的下一个位置

public ListNode reverseBetween(ListNode head, int left, int right) { 
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = head,pre=dummy,tail=dummy;

        //左开右闭(pre，tail]
        int count=0;
        while(count != right){ 
        
        	//left-1,开区间
            if(count == left-1) pre = tail;
            tail = tail.next;
            count++;
        }

        //尾插
        while(pre.next != tail){ 
        
            cur = pre.next;
            pre.next = cur.next;
            cur.next = tail.next;
            tail.next = cur;
        }
        
        return dummy.next;
    }

//栈
public ListNode reverseKGroup(ListNode head, int k) { 
        
        //栈
        Deque<ListNode> stack = new ArrayDeque<ListNode>();
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (true) { 
        
            //tmp遍历指针，head当前区间起点，count表示已放入栈中的数量
            int count = 0;
            ListNode tmp = head;

            //入栈
            while (tmp != null && count < k) { 
        
                stack.add(tmp);
                tmp = tmp.next;
                count++;
            }

            //若不足k结束循环
            if (count != k) { 
        
                //已翻转部分，与剩下不必翻转链表的头结点连接
                p.next = head;
                break;
            }

            //出栈
            while (!stack.isEmpty()){ 
        
                p.next = stack.pollLast();
                p = p.next;
            }

            //已翻转部分，与待翻转头结点连接
            p.next = tmp;
            head = tmp;
        }
        return dummy.next;
    }

//不耗用额外空间，先定位待翻转区间，遍历结点，尾插到初始尾结点后
public ListNode reverseKGroup(ListNode head, int k) { 
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        //待翻转区间（pre,tail]
        ListNode pre = dummy;
        ListNode tail = dummy;
        while (true) { 
        
            int count = 0;
            //定位待翻转区间的尾结点
            while (tail != null && count != k) { 
        
                count++;
                tail = tail.next;
            }
            if (tail == null) break;

            //这一步非常巧妙，将下一次遍历的首结点记录
            ListNode head1 = pre.next;
            while (pre.next != tail) { 
        
                //每移动一个结点，都要相清楚，结点间指向的变化
                ListNode cur = pre.next;
                pre.next = cur.next;
                cur.next = tail.next;
                tail.next = cur;
            }

            //更新下一翻转区间的起始点（首结点）
            pre = head1;
            tail = head1;
        }
        return dummy.next;
    }

tip:一次操作涉及4个结点，都标出来，别搞混乱就行。

tip:考察双指针，注意一定要用虚拟头结点，否则[1]这种只含一个结点的就错误了。

https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/ tip:双指针，如果相交，长的链表的后半部分一定包含短链表的后半部分。两链表末尾对其，从长度差的位置开始遍历，逐一比较。

tip:双指针，求入环位置的结点。

//1.判断链表是否环
//fast每次走两步，slow走一步，能相遇就有环
//2.如果有环，如何找到这个环的入口
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口

1.递归

 public ListNode Merge(ListNode list1,ListNode list2) { 
        
        if(list1 == null){ 
        
            return list2;
        }
        if(list2 == null){ 
        
            return list1;
        }
        if(list1.val <= list2.val){ 
        
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{ 
        
            list2.next = Merge(list1, list2.next);
            return list2;
        }        
    }

2.迭代

    public ListNode Merge(ListNode list1,ListNode list2) { 
        
       if(list1==null){ 
        
            return list2;
        }
  
        if(list2==null){ 
        
            return list1;
        }
        ListNode result = new ListNode(-1);
        ListNode guard = result;
        while(list1!=null && list2!=null){ 
        
  
            if(list1.val<=list2.val){ 
        //同解法一
                result.next = list1;
                list1 = list1.next;
                result = result.next;
            }else if(list1.val>list2.val){ 
        //同解法一
                result.next = list2;
                list2 = list2.next;
                result = result.next;
            }
        }
  
        if(list1==null){ 
        //优化点，剩下的节点全部取list2
            result.next = list2;
        }
  
        if(list2==null){ 
        //优化点，剩下的节点全部取list1
            result.next = list1;
        }
        return guard.next;
    }