实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
使用swift语言解决：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init(_ val: Int) {
* self.val = val
* self.next = nil
* }
* }
*/
class Solution {
func kthToLast(_ head: ListNode?, _ k: Int) -> Int {
var fast = head
// 从1开始到k，那应该包括k
for _ in 1 ... k {
fast = fast?.next
}
var slow = head
while fast != nil {
fast = fast?.next
slow = slow?.next
}
return slow?.val ?? 0
}
}
主要是通过快慢指针快速计算。快指针先把要倒计的次数过掉（1到k,个数为k），这样进行指针向后偏移时，偏移次数就刚好是从正向开始数到要倒计的位置(n - k)，这样再结合一个全链表，让它跟着快指针偏移，这样就刚好得到想要的,当然最好用笔画一下更容易理解。
以下的思路是开始的时候做的：很明显，时间复杂度要高于上面的。
func kthToLast(_ head: ListNode?, _ k: Int) -> Int {
var count = 0
var head1 = head
if head1 != nil {
count += 1
}
while head1?.next != nil{
count += 1
head1 = head1?.next
}
if count == 0 {
return 0
}
var tem = 0
head1 = head
let index = (count - k)
while tem != index {
head1 = head1?.next
tem += 1
}
return head1?.val ?? 0
}
实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点），假定你只能访问该节点。
解题思路：由于单向链表，无法访问前置节点，所有是无法真实删除掉当前节点的，可以采取通过把下一节点的值赋值给当前节点，更新当前节点的值达到删除当前节点的值的目标。
使用java解决：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：核心代码需要指定一个新链表，同时增加一个当前指针指向链表头，然后当前指针为新增节点不断后移，表头指针还在，这样就可以获取到整个链表的数据元素。
// 链表 头指针
let node = ListNode(0)
// 当前指针
var cur = node
// 新增节点
let node1 = ListNode(1)
// 链表的下一个节点指定是新增节点
cur.next = node1
// 当前指针更新为指向新增节点
cur = cur.next
具体解决：
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l11 = l1
var l22 = l2
let node = ListNode(0)
var cur = node
while l11 !=
nil && l22 != nil {
if let v1 = l11?.val, let v2 = l22?.val {
if v1 > v2 {
cur.next = l22
cur = cur.next ?? ListNode(0)
l22 = l22?.next
}else {
cur.next = l11
cur = cur.next ?? ListNode(0)
l11 = l11?.next
}
}
}
if l11 == nil {
cur.next = l22
}else {
cur.next = l11
}
return node.next
}
注意：链表倒置链表核心代码，
var pre:ListNode? = nil
while fast != nil{
let temp = pre
// 这里相当于新创建一个节点，如果用head节点赋值，会让p的next有指向。
pre = ListNode(head?.val ?? 0)
// 头插法 反转
pre?.next = temp
fast = fast?.next
}
真正的倒置应该是把当前节点指针改成指向前面节点。只是通过指针的变化，不新增节点，是最好的，改变原链表是必须的。
var head1 = head;
var nhead: ListNode? = nil;
while head1 != nil {
// 临时存储，不需要全局存储，一个循环就重新赋值
let ntemp = nhead;
// 把原链表当前要处理的节点赋给新链表的头节点，也就是原链表当前要处理的节点多了一个新链表的头指针指向它。
nhead = head1
//接着把原链表的当前节点的下一个节点用原节点头指针缓存，因为下一步会改变当前节点的下一节点的内容为前一节点，防止下一个节点找不到，自然需要缓存，用头节点即可，无需临时指针。
head1 = head1?.next;
//头插法，把当前节点的下节点指向新链表缓存的最新节点。这样就完成了倒置（反转）链表
nhead?.next = ntemp;
}
请判断一个链表是否为回文链表。
两种解法；
- 采取栈来处理
int count = 0;
if (head == null) {
return true;
}
ListNode temp = head;
while (temp != null) {
count ++;
temp = temp.next;
}
Stack<Integer> stack = new Stack();
temp = head;
int i = 0;
boolean flag = true;
for (i = 0; i < count /2; i++) {
stack.push(Integer.valueOf(temp.val));
temp = temp.next;
}
if (count% 2 != 0 ) {
temp = temp.next;
}
ListNode temp1 = temp;
while (!stack.empty()) {
Integer tww = stack.pop();
try {
if (temp.val != tww) {
flag = false;
break;
}else {
temp = temp.next;
}
}catch (NullPointerException e) {
flag = false;
break;
}
}
return flag;
利用快慢指针处理，快指针向后两位移动，慢指针按正常一个一个移动。遍历快指针就可以根据慢指针取得中间位置。遍历过程中如果加上一个指针p把前半链表值倒置，那最后就只需要遍历慢指针，就可以比较p和慢指针节点的值判断。
func isPalindrome(_ head: ListNode?) -> Bool {
if head == nil {
return true
}
var fast = head
var slow = head
// 用来存储前半部分反转链表的指针
var p:ListNode? = nil
while fast != nil && fast?.next != nil {
fast = fast?.next?.next
let temp = p
p = slow
slow = slow?.next
// 头插法 反转
p?.next = temp
}
while fast != nil {
let temp = p
p = slow
p?.next = temp
}
var flag = true
while p != nil {
if p?.val != slow?.val {
flag = false
break
}
slow = slow?.next
}
return flag
}
剑指 Offer 52. 两个链表的第一个公共节点
问题思路需要捋一下。
