面试题-链表(1)

1.移除链表元素：

203. 移除链表元素 - 力扣（LeetCode）

删除一个链表中的相同元素。

我这里用的方法只需要将链表遍历一次，就可以删除所有节点。

前后指针法:

public ListNode removeElements(ListNode head, int val) {
//先判断链表不为空 
if(head==null){return head;}
ListNode prev=head;//前指针
ListNode cur=head.next;//后指针
while(cur!=null)//开始遍历链表,用cur遍历，如果用prev遍历链表，到最后prev为null时，cur已经越界if(cur.val==val){//该节点等于val(应被删除的节点)prev.next=cur.next;//跳过该节点cur=cur.next;//cur继续往后遍历}else{//该节点不等于valprev=cur;//prev往后遍历cur=cur.next;//cur往后遍历}
//上面只遍历了第二个节点以及后面的节点，并没有遍历第一个节点，所以单独判断
if(head.val==val){head=head.next;}
return head;//返回头节点
}

2.反转链表：

206. 反转链表 - 力扣（LeetCode）

 

public ListNode reverseList(ListNode head) {
if(head==null){//如果链表是空链表就提前返回return null;
}
ListNode cur =head.next;//定义一个cur节点，可以找到head的下一个节点
head.next=null;//将头节点的next置为null
while(cur!=null){//开始遍历链表，同时反转链表
ListNode curN=cur.next;//定义一个curN，找到cur的下一个节点
cur.next=head;//开始反转链表
head=cur;
cur=curN;
}
return head;}

3.链表中间节点：

876. 链表的中间结点 - 力扣（LeetCode）

如果是奇数个节点：则返回中间的节点

如果是偶数个节点：则返回中间的第二个节点

 这里我介绍一个很经典的方法：快慢指针（通俗说话）

定义一个slow节点和一个fast节点，都指向head节点，然后遍历链表，slow往后走一步，fast往后走两步，直到fast.next==null（奇数个节点的情况）或者fast==null（偶数个节点的情况）

public ListNode middleNode(ListNode head){
if(head==null){//如果链表是空则提前返回
return null;}
ListNode slow=head;
ListNode fast=head;
while(fast!=null&&fast.next!=null){//开始遍历链表,如果fast==null，fast.next就会出现引用空指针而报错，所以括号里面的顺序不能变
slow=slow.next;//slow每次往后走一步
fast=fast.next.next;//fast每次往后走两步}
return slow;
}

4.返回倒数第k个节点：

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

  

 public int kthToLast(ListNode head, int k) {if(head==null){//如果链表为空提前返回return -1;}ListNode slow=head;ListNode fast=head;int count=0;while(count!=k-1){//开始移动fast节点fast=fast.next;count++;}while(fast.next!=null){//slow指针和fast指针一起往后遍历slow=slow.next;fast=fast.next;}return slow.val;}