【无标题】力扣链表总结

k个一组反转链表（25）

前置知识1.2.

1. 反转整个链表

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != null) {
nxt = cur.next;
// 逐个结点反转
cur.next = pre;
// 更新指针位置
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

2. 给定开始结点和结束结点反转链表
   上面是因为结束结点为空，所以while循环是cur！=null，如果结束结点不为空，则while循环中条件是cur！=b,a到b是左闭右开转态
   将结束结点带入循环内判断就行了

// 反转以a到b之间的链表
ListNode reverse(ListNode a,ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != b) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

3. 进行解题思路

1、找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
2、对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭又开区间，所以本轮操作的尾结点其实就是下一轮操作的头结点）。
3、对下一轮 k 个节点也进行翻转操作。
4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。

4. K个一组反转

ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        // 区间 [a, b) 包含 k 个待反转元素
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // 不足 k 个，不需要反转，base case
            if (b == null) return head;
            b = b.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(a, b);
        // 递归反转后续链表并连接起来
        a.next = reverseKGroup(b, k);
        return newHead;
    }

    ListNode reverse(ListNode a, ListNode b) {
        ListNode pre, cur, nxt;
        pre = null; cur = a; nxt = a;
        // while 终止的条件改一下就行了
        while (cur != b) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }

环形链表（141）

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null)
        return false;
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

环形链表||(142)

解题思路参考https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
参考了它的代码
使用快慢指针。快的每次走两步，慢的每次走一步。
另一种清晰的解释

L=N*C-X
也就是说，head与相遇点的指针同时向后移动，相遇时，就是环的入口。（令N=1）

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while(true){
            if(fast==null||fast.next==null)return null;
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)break;

        }
        fast=head;
        while(slow!=fast){
                slow=slow.next;
                fast=fast.next;
        }
        return fast;
        
    }
}

测试代码及结果

	 public static ListNode detectCycle(ListNode head) {
	        ListNode fast=head;
	        ListNode slow=head;
	        while(true){
	            if(fast==null||fast.next==null)return null;
	            fast=fast.next.next;
	            slow=slow.next;
	            if(fast==slow)break;

	        }
	        fast=head;
	        while(slow!=fast){
	                slow=slow.next;
	                fast=fast.next;
	        }
	        return fast;
	        
	    }
	 public static void main(String[] args) {
		 //构造一个环形链表，5-3-2-7-1-6-8-9-4-1，环的入口在1
			ListNode node1=new ListNode(5);
			ListNode node2=new ListNode(3);
			ListNode node3=new ListNode(2);
			ListNode node4=new ListNode(7);
			ListNode node5=new ListNode(1);
			ListNode node6=new ListNode(6);
			ListNode node7=new ListNode(8);
			ListNode node8=new ListNode(9);
			ListNode node9=new ListNode(4);
			node1.next=node2;
			node2.next=node3;
			node3.next=node4;
			node4.next=node5;
			node5.next=node6;
			node6.next=node7;
			node7.next=node8;
			node8.next=node9;
			node9.next=node5;
			System.out.println(detectCycle(node1).val);//输出1		
		}