1.删除链表中等于给定值val的所有节点。
解题思路：遍历链表，查找到给定值节点，删除改节点，即使改节点的上一个节点指向下下一个节点。
class ListNode{
int val=0;
ListNode next=null;
public ListNode(){
}
public ListNode(int val){
this.val=val;
this.next=null;
}
public ListNode(int val,ListNode next){
this.val=val;
this.next=next;
}
}
//删除链表中的指定元素
public static ListNode removeElements(ListNode head,int val){
if(head==null){
return null;
}
ListNode prev=head;
ListNode cur=head.next;
for (;cur!=null;){
if (cur.val==val){
prev.next=cur.next;
cur=prev.next;
}else {
prev=prev.next;
cur=cur.next;
}
}
if(head.val==val){
head=head.next;
}
return head;
}2.反转一个单链表。
解题思路：
创建prevNode=null newHead=null currentNode=head
在循环中，currentNode.next=null,的时候找到反转链表的新节点 newHead也就是原链表的最后一个节点。
之后使得 第一个节点currentNode指向null（prevNode）
prevNode=currentNode 当前节点（第一个节点）
currentNode=nextNode 下一个节点
如此循环 ，即可实现链表的反转。
public static ListNode reverseList(ListNode head){
if(head==null){
return null;
}
if (head.next==null){
return head;
}
ListNode prevNode=null;
ListNode newHead=null;
ListNode currentNode=head;
while (currentNode!=null){
ListNode nextNode=currentNode.next;
if (nextNode==null){
newHead=currentNode;
}
currentNode.next=prevNode;
prevNode=currentNode;
currentNode=nextNode;
}
return newHead;
}
3.
给定一个带有头结点 head
的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
解题思路：
获取链表长度 ，获取链表长度的一半再遍历即可。
public int getLength(ListNode head){
int length=0;
//遍历链表
for (ListNode cur=head;cur!=null;cur=cur.next){
length++;
}
return length;
}
public ListNode middleNode(ListNode head){
if (head==null){
return null;
}
int len=getLength(head)/2;
ListNode cur=head;
for (int i=0;i<len;i++){
cur=cur.next;
}
return cur;
}
4.
输入一个链表，输出该链表中倒数第
k
个结点。
解题思路：
首先判断一下成立条件
获取链表的长度len len-k就是该节点的位置
链表从头开始走，走len-k步就是该节点
public ListNode FindKthToTail(ListNode head,int k){
if (head==null){
return null;
}
if (k<=0){
return null;
}
int len=getLength(head);
if (k>len){
return null;
}
int steps=len-k;
ListNode cur=head;
for (int i=0;i<steps;i++){
cur=cur.next;
}
return cur;
}
5.
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：
定义一个新链表，创建傀儡节点便于后续插入
在两个链表不为空的条件下，对比两个链表 节点值的大小
如果cur1的值比cur2的值小，那么cur1链表的值就首先插入到新链表当中，反之则插入cur2（这里注意不要忘记更新链表节点）
如果cur1链表插入完成，就将剩余的cur2链表的剩余节点都插入到新链表，反之则将cur1的剩余节点全部插入到新链表。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1==null){
return l2;
}
if (l2==null){
return l1;
}
ListNode cur1=l1;
ListNode cur2=l2;
ListNode newHead=new ListNode(0);
ListNode newTail=newHead;
while (cur1!=null && cur2!=null){
if (cur1.val<cur2.val){
newTail.next=cur1;
cur1=cur1.next;
}else {
newTail.next=cur2;
cur2=cur2.next;
}
if (cur1==null){
newTail.next=cur2;
}else{
newTail.next=cur1;
}
}
return newHead.next;
}6.
编写代码，以给定值
x
为基准将链表分割成两部分，所有小于
x
的结点排在大于或等于
x
的结点之前。
解题思路：
定义两个新链表，使用傀儡节点简化插入操作
将所有小于X 的值插入smallTail，反之插入largeTail，
最终再将两个链表合并，使得smallTail.next=largeTail即可。
public ListNode partition(ListNode pHead, int x) {
if (pHead==null){
return null;
}
if (pHead.next==null){
return pHead;
}
ListNode smallHead=new ListNode(0);
ListNode smallTail=smallHead;
ListNode largeHead=new ListNode(0);
ListNode largeTail=largeHead;
for (ListNode cur=pHead;cur!=null;cur=cur.next){
if (cur.val<x){
smallTail.next=new ListNode(cur.val);
smallTail=smallHead.next;
}else {
largeTail.next=new ListNode(cur.val);
largeTail= smallTail.next;
}
}
smallTail.next=largeTail;
return smallHead.next;
}
版权声明：本文为curelmn原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。