（尊重劳动成果，转载请注明出处：https://yangwenqiang.blog.csdn.net/article/details/105692949冷血之心的博客）
这段时间完成了职业生涯第一次跳槽，对算法题目有了一个更深的认识和理解，这里将链表常见的面试题目以及解法补充完善。
链表基础题大全（四）：单链表相加 & 复制带随机指针的链表 &判断回文链表
在前面两个小节的介绍中，我们主要介绍了基础的链表题目，主要是利用了双指针的思想。本篇博文，我们来看两道经典的题目：奇偶链表和旋转链表。
奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入：1->2->3->4->5->NULL
输出：1->3->5->2->4->NULL
示例 2:
输入：2->1->3->5->6->4->7->NULL
输出：2->3->6->7->1->5->4->NULL
说明：
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
思路：
还算比较清晰吧，我们使用一个while循环遍历一遍链表，然后分别将奇数节点和偶数节点串起来，完事儿~
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head==null||head.next==null)
return head;
//保存头节点
ListNode dummyHead = head;
ListNode node = head.next;
//保存第一个偶数节点
ListNode nextNode = head.next;
while (node != null && node.next != null) {
//依次将奇数节点链接起来
head.next = head.next.next;
head = head.next;
//依次将偶数节点链接起来
node.next = node.next.next;
node = node.next;
}
//将第一个偶数节点链接到最后一个奇数节点的后面
head.next = nextNode;
return dummyHead;
}
}
旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入：1->2->3->4->5->NULL, k = 2
输出：4->5->1->2->3->NULL
解释:
向右旋转 1 步：5->1->2->3->4->NULL
向右旋转 2 步：4->5->1->2->3->NULL
示例 2:
输入：0->1->2->NULL, k = 4
输出：2->0->1->NULL
解释:
向右旋转 1 步：2->0->1->NULL
向右旋转 2 步：1->2->0->NULL
向右旋转 3 步：0->1->2->NULL
向右旋转 4 步：2->0->1->NULL
思路：
- 根据题意，既然是旋转链表，有一种情况是旋转之后是其本身，这里需要特殊判断。
- 然后我们需要做的就是通过双指针将链表分为前后两个部分，找到最终结果中的最后一个节点，也就是前半部分的最后一个节点；
- 然后再找到后半部分的最后一个节点，将后半部分最后一个节点指向head节点
- 然后就拼接完成啦~
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null||k<=0)
return head;
int step = k%getDepth(head);
// 这块表示旋转之后还是本身
if(step==0)
return head;
ListNode left = head;
ListNode right = head;
while(step>0){
right = right.next;
step--;
}
// 同时出发
while(right.next!=null){
left = left.next;
right = right.next;
}
// 这个时候，left就是旋转之后的最后一个节点
ListNode reHead = left.next;
left.next=null;
// 找到后半部分的最后一个节点
ListNode reCur = reHead;
while(reCur.next!=null){
reCur = reCur.next;
}
// 将后半部分最后一个节点指向head节点
reCur.next = head;
// 拼接完成
return reHead;
}
private int getDepth(ListNode head){
int count = 0;
while(head!=null){
count++;
head = head.next;
}
return count;
}
总结：
奇偶链表和旋转链表也是常见的高频单链表题目，主要考察对于指针的操作（奇偶链表）以及双指针的使用（旋转链表），希望大家可以有效掌握与理解，看不懂的可以在纸上自己举个例子哈。
后续继续更新面试中常见的链表题目，欢迎大家关注~
注意啦，注意啦~
欢迎大家关注我的牛客专栏：《Java开发岗面试题全解析》 ，点击图片查看详情。
Java开发岗高频面试题全解析，专栏共计32节，已经全部更新完毕。
专栏分9个模块来对Java岗位面试中的知识点进行解析，包括通用面试技能，Java基础，Java进阶，网络协议，常见框架以及算法，设计模式等。
专栏串点成面的解析每个面试题背后的技术原理，由浅入深，循序渐进，力争让大家掌握面试题目的背后的技术原理，摒弃背题模式的陋习。
如果对你有帮助，记得点赞哈，欢迎大家关注我的博客，关注公众号（文强的技术小屋），学习更多技术知识，一起遨游知识海洋~
转载：https://blog.csdn.net/qq_25827845/article/details/105692949