lt.24. 两两交换链表中的节点
[案例需求]
[思路分析一, 迭代法]
- 艹, 自己半年独立写的一道题, 再写一次过不了了还. 蛋疼!
[代码实现]
// 1. 迭代解法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
//
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode temp = dummyNode;
while(temp.next != null && temp.next.next != null){
//两两交换
ListNode cur_left = temp.next;
ListNode cur_right = temp.next.next;
temp.next = cur_right;
cur_left.next = cur_right.next;
cur_right.next = cur_left;
temp = cur_left;
}
return dummyNode.next;
}
}
[思路分析二, 递归法]
- 参见: 点我
[代码实现]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null)return head;
ListNode next = head.next;
head.next = next.next;
next.next = head;
head.next = swapPairs(head.next);
return next;
}
}
lt.61. 旋转链表
[案例需求]
[思路分析]
[代码实现]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null) return head;
//遍历出链表的长度
ListNode lenNode= head;
int count = 1;
while(lenNode.next != null){
count++;
lenNode = lenNode.next;
//lenNode 可以作为尾结点
}
//特判
if(k % count == 0) return head;
//找到第 count - k - 1个结点
int j = count - (k % count);
ListNode preNode = head;
while(j > 1){
preNode = preNode.next;
j--;
}
//此时pre.next == 待旋转链表的第一个结点的前一个结点
lenNode.next = head;
head = preNode.next;
preNode.next = null;
return head;
}
}
