链表算法题:其实这类题最简单的解法就是画图,图出来,题结束.在这里我只给出具体算法代码,就不测试了.等我学会使用动图,我会全部进行修改的.

• 1.反转链表.
• 2.链表的中间节点.

1.反转链表.

输入:head=[1,2,3,4,5]
输出:[5,4,3,2,1]
具体实现方法:
刚开始,我们新建一个节点cur让他指向原始链表的head节点.(ListNode cur=head)
prev节点用来保存cur的前一个节点,刚开始设为null .(ListNode prev=null)
定义一个newNode节点,用来保存cur的后一个节点.刚开始也设置为null.
接下来我们进行逆置操作:
a.先进行判断,当 cur!=null 时进入循环.
代码实现:while(cur!=null)
b. 用newNode保存cur的下一个节点
代码实现:newNode=cur.next,
c.用cur指向前一个节点
代码实现:cur.next=prev,
d.此时让prev右移到cur的位置,将cur右移到newNode的位置.
代码实现:prev=cur;cur=newNode.
第一次在循环中图形展示(执行b,c两个步骤):
newNode=cur.next;
cur.next=prev;

第一次循环结束后图形展示(执行d步骤后):
prev=cur;
cur=newNode.

第二次在循环中图形展示(执行b,c两个步骤):
newNode=cur.next;
cur.next=prev;

第二次循环结束后图形展示(执行d步骤后):
prev=cur;
cur=newNode.

然后再进入下次循环.重复上面步骤,等到cur到第五个节点的位置进入循环时:

至此循环结束,链表反转完成.返回prev.

具体代码展示:

public class ListNode{
	int val;
	ListNode next;
	ListNode(int val) { this.val = val; }
}
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
        //用来保存cur的前一个节点.
        ListNode prev=null;
        //用来保存cur的后一个节点
        ListNode newNode=null;
        while(cur!=null){
        	//将newNode右移,放在cur的下一个节点位置.
            newNode=cur.next;
            //将cur的next指向前一个节点prev的位置
            cur.next=prev;
            //将prev右移放到cur的位置
            prev=cur;
            //将cur右移放到newNode的位置.
            cur=newNode;
        }
        //返回prev.
        return prev;
    }
}

2.链表的中间节点.

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例:输入[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 .
因为我们返回的是一个ListNode对象.所以会打印出3以后的序列链表.

思路: 采用快慢指针的思想,定义两个指针fast,slow开始都放在head的位置.让fast每次走两步,slow每次走一步:
fast=fast.next.next; slow=slow.next;

当链表中元素个数为奇数时:fast走到最后,fast.next刚好为null跳出循环,slow此时刚好走到中间位置.此时返回slow.(fast1为第一步,fast2为第二步.下面slow一样.)
图形展示:

当链表中元素个数为偶数时,fast走到最后时刚好为null跳出循环,slow刚好走到中间两个节点中第二个节点的位置.此时返会slow.
图形展示:

具体代码展示:

public class ListNode{
	int val;
	ListNode next;
	ListNode(int val) { this.val = val; }
}
class Solution {
    public ListNode middleNode(ListNode head) {
    	//定义快慢两个指针.
        ListNode fast=head;
        ListNode slow=head;
        //fast不能为空,fast.next也不能为空,否则会报空指针异常.
        while(fast!=null&&fast.next!=null){
        	//fast每次走两步.
            fast=fast.next.next;
            //slow每次走一步.
            slow=slow.next;
        }
        return slow;
    }
}