Linked List链表类题目的解题模板

佚名 4年前 (2020-06-18) 算法 1001人围观抢沙发百度已收录

B站图灵星球的视频总结的文档，传送门
基本都是双指针法，一个移动快，一个移动慢。

定义

 public class ListNode {
	 int val;
 	 ListNode next;
 	 ListNode(int x){ val = x; }
	 }

1. Linked List找中间节点

两个指针同向而行，一个每次前进2个节点，另一个每次前进1个节点，当快指针到最后，慢指针就停留在中点。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

public ListNode LinkedListMiddleNode (ListNode head){
	ListNode i = head; 
    ListNode j = head;
	while(j != null && j.next != null){
		i = i.next;
		j = j.next.next;
	}
	return i;
    }

2. Linked List找倒数第K个节点(LeetCode面试题02.02）

先使两个指针相隔K个位置，然后使每次以相同的速度向前移动，当快指针出界时候，慢指针就停留在倒数第K个位置

public ListNode LinkedListLastKthNode(ListNode head,int k){ 
    ListNode i = head;
    ListNode j = head;
    for(int a = 0; a < k; a++){ 
        j = j.next; //使i和j相隔K个节点
    }
    while(j != null){ 
        i = i.next;
        j = j.next; 
    }
        return i; 
}

3. 反转链表(LeetCode面试题24）

可以使用递归或者迭代。
1->2->3->4->5反转后变为1<-2<-3<-4<-5

public ListNode reverse(ListNode head){ 
    if(head == null || head.next == null){ 
        return head; 
        ListNode reversed_head = reverse(head.next); 
        head.next.next = head; 
        head.next = null; 
        return reversed_head;
    }
}