leetcode 链表

实现一种算法，找出单向链表中倒数第 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
         for _ in 1 ..< k {
            fast = fast?.next
         }
         var slow = head
         while fast?.next != nil {
              fast = fast?.next
              slow = slow?.next
         }
         return slow?.val ?? 0
    }
}

主要是通过快慢指针快速计算。快指针先把要倒计的次数过掉，这样进行指针向后偏移时，偏移次数就刚好是从正数到要倒计的位置，这样再结合一个全链表，让它跟着快指针偏移，这样就刚好得到想要的。
以下的思路是开始的时候做的：很明显，时间复杂度要高于上面的。

 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 p:ListNode? = nil
 while head != nil{
           
            let temp = p
            p = head
            // 头插法 反转
            p?.next = temp
           head = head?.next
        }

请判断一个链表是否为回文链表。
两种解法；

1. 采取栈来处理

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
    }